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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
11
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 3:00

Your Answer

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

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