3
$\begingroup$

Graph Isomorphism is natural problem which is most widely believed to have intermediate complexity between $P$ and $NP$-complete. GI can be thought as deciding the existence of an isomorphism between two sets of node pairs. I'm trying to develop a notion of isomorphism between sets of triples.

We are given two hyper-graphs $G1$ and $G2$ such that the set of hyperedges ($E_1$ and $E_2$) consists of triples of 3 nodes $\{t_1, t_2, t_3 \}$. We say that Hyper-graphs $G1$ and $G2$ are isomorphic if there is bijection $f$ from $V_1$ to $V_2$ such that pair $\{u,v\} \in E1 $ if and only if $\{f(u),f(v) \} \in E2 $. We say $\{u, v \} \in E $ if there is a triple (hyperedge) $\{ u, v, z\} \in E$ for some node $z$.

Is it $NP$-complete to decide the existence of such isomorphism between two hyper-graphs $G1$ and $G2$?

$\endgroup$
8
$\begingroup$

Your problem reduces to graph isomorphism, so is not $\mathsf{NP}$-complete unless the polynomial hierarchy collapses.

In fact, you've essentially already given the reduction in your question: given a 3-uniform (=every hyperedge has size 3) hypergraph $G$, construct from it the graph $f(G)$ which has the same vertex set, and such that $\{u,v\} \in E(f(G))$ iff there exists a $z \in V$ such that $\{u,v,z\} \in E(G)$. (When $G$ is a hypergraph, I use $E(G)$ to mean the set of hyperedges.) Then $G_1$ and $G_2$ are isomorphic-in-your-sense iff $f(G_1) \cong f(G_2)$ as graphs. It is not hard to check that this reduction only takes polynomial time (note that $|E(f(G))| \leq |V(G)| |E(G)|$).

It is also probably worth mentioning that there is already a well-established notion of hypergraph isomorphism that is different from your notion. If we consider a hypergraph $G$ as a vertex set $V$ together with a collection of hyperedges $E \subseteq P(V)$ (each hyperedge is a subset of $V$), then two such hypergraphs are isomorphic if there is a bijection $\pi\colon V_1 \to V_2$ such that $E_2 = \pi(E_1)$. (Here I am abusing notation twice: by "$\pi(E_1)$" I mean $\{\pi(e) : e \in E_1\}$ and by $\pi(e)$ for $e \subseteq V$ I mean $\{\pi(v) : v \in e\}$.) Hypergraph isomorphism in this sense is Karp-equivalent to graph isomorphism, but by a slightly less immediate reduction than from your problem. However, fast (in theory) algorithms for hypergraph isomorphism are often more difficult than those for graph isomorphism (see, e.g. Babai and Codenotti, FOCS 2008).

$\endgroup$
  • $\begingroup$ So, in my notion triple $\{ 1,2,3\}$ is mapped to triple$ \{1,2,6\}$ but in standard isomorphism triple $\{ 1,2,3\}$ is mapped to triple$ \{1,2,3\}$. You are saying those lead to equivalent notions. Am I missing something? $\endgroup$ – Mohammad Al-Turkistany Jun 26 '13 at 21:53
  • $\begingroup$ Pair $\{u,v\} \in E1 $ if and only if $\{f(u),f(v) \} \in E2 $ is equivalent to saying that triple with pair $\{u,v\} \in E1 $ if and only if triple with pair $\{f(u),f(v) \} \in E2 $. This is because pairs only occur inside triples (hyperedges). $\endgroup$ – Mohammad Al-Turkistany Jun 26 '13 at 22:20
  • 1
    $\begingroup$ I didn't quite follow your first comment, but the standard notion of iso (as in the 3rd paragraph of my answer) is definitely not the same as your notion. Consider G1 on 6 vertices consisting of the hyperedges {1,2,4}, {2,3,5}, {1,3,6} and G2 on 6 vertices to consist of the hyperedges in G1 in addition to the hyperedge {1,2,3}. In your notion, these two are "isomorphic" but they are definitely not isomorphic in the usual sense, for they have a different number of hyperedges. $\endgroup$ – Joshua Grochow Jun 27 '13 at 2:49
  • $\begingroup$ Here's a more complicated example where they have the same number of hyperedges, are isomorphic in your sense, but not in the usual sense. For brevity I omit commas in triples. Verts are labelled a,b,c,...,j. Let S = {abc, bde, cef, egh, fhi, hij} be a set of triples. Then H1 = S union {bec} and H2 = S union {efh}. $\endgroup$ – Joshua Grochow Jun 27 '13 at 3:00
  • 1
    $\begingroup$ The point is that your notion is essentially considering the 1-skeleton of a 2-dimensional simplicial complex, but forgets which triangles are 2-simplices or are "unfilled" triangles. The usual notion of hypergraph iso coincides with the notion of iso for simplicial complexes. $\endgroup$ – Joshua Grochow Jun 27 '13 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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