This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work and what is its complexity. If I understand the post in the link correctly, the reduction has to be polynomial in order for the Hyper-graph isomorphism solution to inherit the same complexity as the Graph-isomorphism problem. Is the reduction only valid for a special case of the Hypergraph isomorphism problem or in general?


1 Answer 1


A description is given in the first paragraph of [1], where HI stands for Hypergraph Isomorphism and GI for Graph Isomorphism:

Given a pair of hypergraphs $X=(V,E)$ and $X'=(V',E')$ as instance for HI, the reduced instance of GI consists of two corresponding bipartite graphs $Y$ and $Y'$ defined as follows. The graph $Y$ has vertex set $V \uplus E$ and edge set $E(Y) = \{\{v,e\} \mid v \in V, e \in E, v \in e\}$, and $Y'$ is defined similarly. Here, $C \uplus D$ denotes the disjoint union of the sets $C$ and $D$. It is easy to verify that $Y \simeq Y'$ if and only if $X \simeq X'$ assuming that $V$ can be mapped only to $V'$ and $E$ can be mapped only to $E'$. This latter condition is easy to enforce.

The other direction is trivial as every graph is also a hypergraph.

[1] Arvind, Vikraman, Bireswar Das, Johannes Köbler, and Seinosuke Toda. "Colored hypergraph isomorphism is fixed parameter tractable." Algorithmica 71, no. 1 (2015): 120-138.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.