<p>It depends on whether the uniformity of your hypergraphs is bounded.</p>

<p><strong>Bounded uniformity</strong> In this case, you can represent each hypergraph with a colored bipartite graph which has vertices on one side (colored blue) and hyperedges on the other side (colored red). A vertex and a hyperedge are connected if the hyperedge connects the vertex. We can get rid of the colors in any number of ways, for example attach to each red a vertex a very long path which will force any isomorphism between two such graphs to match vertex colors. These graphs have bounded degree, and so GI for this class of graphs is in P.</p>

<p><strong>Unbounded uniformity</strong> In this case the problem is GI-complete. Given a graph $G$, create a bounded degree hypergraph whose vertices are the edges of $G$ and whose hyperedges correspond to vertices of $G$; a hyperedge contains a vertex if the corresponding vertex of $G$ belongs to the corresponding edge of $G$. This hypergraph has maximum degree 2. Two graphs are isomorphic if and only if the corresponding hypergraphs are isomorphic (this requires some argument but seems correct).</p>

CC BY-SA 3.0
2017-09-04T17:23:03.593Z
This is not taken from any paper. Still, the main ideas seem reasonable enough, though it's worthwhile to check the details.
Yuval Filmus
CC BY-SA 3.0
2017-09-05T05:41:27.627Z
Indeed, I believe your reduction in the second case factors as: first reduce GI to bipartite GI by putting a new vertex on every edge, then use the equivalence between bipartite GI and hypergraph iso (being careful about which side of your bipartite graph you turn into the hyperedges and which into the vertices).
Joshua Grochow
CC BY-SA 3.0
2017-09-04T12:09:03.543Z
2017-09-04T12:09:03.543Z
Yuval Filmus
<p>Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices.</p>

<p>A <strong>hyper graph</strong> G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain subsets of the vertex set of $V$. An example of hyper-graph is given below and for example edge $e_3$ is a subset contain $v_3,v_5,v_6$ and similarly for other edges.</p>

<p><a href="https://i.sstatic.net/fl7Wr.png" rel="noreferrer"><img src="https://i.sstatic.net/fl7Wr.png" alt="enter image description here"></a></p>

<p><strong>Isomorphism</strong> : 
Two hyper graphs $G(V,E)$ and $H(V,E')$ are isomorphic if there is a permutation $g$ on $V$ such that,  $\forall $ $e \in E$, $$e\in E \iff g(e) \in E'$$</p>

<p><strong>Reference</strong>: <a href="https://en.wikipedia.org/wiki/Hypergraph" rel="noreferrer">https://en.wikipedia.org/wiki/Hypergraph</a></p>

<p>Let me define the degree of a <strong>vertex</strong> in a hyper-graph:</p>

<p>$$D_v = |\{e_i \mid v\in e_i, e_i \in E\} |$$</p>

<p><strong>Question</strong> : Is Isomorphism of bounded degree hyper-graphs in P ?</p>

<reference-request><soft-question>
Is Isomorphism of bounded degree hyper-graphs in P?
new
# Is Isomorphism of bounded degree hyper-graphs in P?

(Asked by: username_0 on 2017-09-04)

Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices.

A **hyper graph** G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain subsets of the vertex set of $V$. An example of hyper-graph is given below and for example edge $e\_3$ is a subset contain $v\_3,v\_5,v\_6$ and similarly for other edges.

[![enter image description here](https://i.sstatic.net/fl7Wr.png)](https://i.sstatic.net/fl7Wr.png)

**Isomorphism** :
Two hyper graphs $G(V,E)$ and $H(V,E')$ are isomorphic if there is a permutation $g$ on $V$ such that, $\forall $ $e \in E$, $$e\in E \iff g(e) \in E'$$

**Reference**: <https://en.wikipedia.org/wiki/Hypergraph>

Let me define the degree of a **vertex** in a hyper-graph:

$$D\_v = |\{e\_i \mid v\in e\_i, e\_i \in E\} |$$

**Question** : Is Isomorphism of bounded degree hyper-graphs in P ?

**Tags:** reference-request, soft-question


---

## 1 answers

### Answer by username_1 on 2017-09-04. Score: 7 | Accepted answer

It depends on whether the uniformity of your hypergraphs is bounded.

**Bounded uniformity** In this case, you can represent each hypergraph with a colored bipartite graph which has vertices on one side (colored blue) and hyperedges on the other side (colored red). A vertex and a hyperedge are connected if the hyperedge connects the vertex. We can get rid of the colors in any number of ways, for example attach to each red a vertex a very long path which will force any isomorphism between two such graphs to match vertex colors. These graphs have bounded degree, and so GI for this class of graphs is in P.

**Unbounded uniformity** In this case the problem is GI-complete. Given a graph $G$, create a bounded degree hypergraph whose vertices are the edges of $G$ and whose hyperedges correspond to vertices of $G$; a hyperedge contains a vertex if the corresponding vertex of $G$ belongs to the corresponding edge of $G$. This hypergraph has maximum degree 2. Two graphs are isomorphic if and only if the corresponding hypergraphs are isomorphic (this requires some argument but seems correct).

> **Comments:**
> **username_1**: This is not taken from any paper. Still, the main ideas seem reasonable enough, though it's worthwhile to check the details.  
> **username_2**: Indeed, I believe your reduction in the second case factors as: first reduce GI to bipartite GI by putting a username_0 vertex on every edge, then use the equivalence between bipartite GI and hypergraph iso (being careful about which side of your bipartite graph you turn into the hyperedges and which into the vertices).  

---

