# Is Isomorphism of bounded degree hyper-graphs in P?

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. 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 ?

## 1 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).

• This is not taken from any paper. Still, the main ideas seem reasonable enough, though it's worthwhile to check the details. – Yuval Filmus Sep 4 '17 at 17:23
• 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 Sep 5 '17 at 5:41