# How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?

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?

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.