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

<p>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)|$). </p>

<p>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. <a href="http://dx.doi.org/10.1109/FOCS.2008.80">Babai and Codenotti, FOCS 2008</a>).</p>

CC BY-SA 3.0
2013-06-26T21:53:26.130Z
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?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-26T22:20:51.133Z
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).
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-27T02:49:19.823Z
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.
Joshua Grochow
CC BY-SA 3.0
2013-06-27T03:00:01.837Z
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}.
Joshua Grochow
CC BY-SA 3.0
2013-06-27T03:00:23.463Z
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.
Joshua Grochow
CC BY-SA 3.0
2013-06-27T11:42:31.950Z
Thanks Grochow for elaborating. So, even that they are not equivalent but you say they are computationaly equivalent? Can you point me to a reference for Isomorphism of simplical complexes?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-27T12:17:44.287Z
Basiclly, you say $\{ u,v, z\} \in E1$  if and only if $\{f(u),f(v), f(z) \} \in E2$  gives computationaly equivalent notion of isomorphism to $\{ u,v, z\} \in E1$  if and only if $\{f(u),f(v), w \} \in E2$? Am I right in my conclusion?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-28T16:58:26.223Z
The Babai--Codenotti paper and references therein are good for hypergraph iso, but I actually don't know a good ref for iso of simplicial complexes. A simplicial complex is just a hypergraph that is downward closed, i.e. if $e \subseteq V$ is a hyperedge of $G$ and $f \subseteq e$, then $f$ must also be a hyperedge of $G$. So every hypergraph iso algorithm automatically applies to simplicial complexes. I don't know if there are any techniques for simplicial complex iso that aren't just hypergraph iso, but would be interested if there were.
Joshua Grochow
CC BY-SA 3.0
2015-12-10T17:07:34.990Z
@JoshuaGrochow Could GI be equivalent to a NP complete promise problem (it cannot be NP complete unless PH collapses)? Is there any consequences?
Turbo
CC BY-SA 3.0
2015-12-10T17:20:31.657Z
@Turbo: This should be a separate question.
Joshua Grochow
CC BY-SA 3.0
2015-12-10T17:22:13.827Z
@JoshuaGrochow I am not sure if it is a research problem so I posted here http://cs.stackexchange.com/questions/50570/on-equivalences-to-promise-problem
Turbo
CC BY-SA 3.0
2013-06-26T20:25:26.777Z
2013-06-26T20:25:26.777Z
Joshua Grochow
<p>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. </p>

<p>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$.   </p>

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

<cc.complexity-theory><graph-theory>
Isomorphism notion between sets of triples
Mohammad Al-Turkistany
# Isomorphism notion between sets of triples

(Asked by: username_0 on 2013-06-26)

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

**Tags:** cc.complexity-theory, graph-theory


---

## 1 answers

### Answer by username_1 on 2013-06-26. Score: 8 | Accepted answer

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](http://dx.doi.org/10.1109/FOCS.2008.80)).

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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).  
> **username_1**: 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.  
> **username_1**: 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}.  
> **username_1**: 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.  
> **username_0**: Thanks Grochow for elaborating. So, even that they are not equivalent but you say they are computationaly equivalent? Can you point me to a reference for Isomorphism of simplical complexes?  
> **username_0**: Basiclly, you say $\{ u,v, z\} \in E1$  if and only if $\{f(u),f(v), f(z) \} \in E2$  gives computationaly equivalent notion of isomorphism to $\{ u,v, z\} \in E1$  if and only if $\{f(u),f(v), w \} \in E2$? Am I right in my conclusion?  
> **username_1**: The Babai--Codenotti paper and references therein are good for hypergraph iso, but I actually don't know a good ref for iso of simplicial complexes. A simplicial complex is just a hypergraph that is downward closed, i.e. if $e \subseteq V$ is a hyperedge of $G$ and $f \subseteq e$, then $f$ must also be a hyperedge of $G$. So every hypergraph iso algorithm automatically applies to simplicial complexes. I don't know if there are any techniques for simplicial complex iso that aren't just hypergraph iso, but would be interested if there were.  
> **username_2**: @JoshuaGrochow Could GI be equivalent to a NP complete promise problem (it cannot be NP complete unless PH collapses)? Is there any consequences?  
> **username_1**: @username_2: This should be a separate question.  
> **username_2**: @JoshuaGrochow I am not sure if it is a research problem so I posted here http://cs.stackexchange.com/questions/50570/on-equivalences-to-promise-problem  

---

