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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.