Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Show that ISO ∈ NP.
In order to solve this problem, I created a non-deterministic Turing machine that did the following:
- Check if each graph has the same number of nodes
- Non-deterministically arrange the edges of G in a permutation that matches H
- Verify that each edge in the permutation of G matches the corresponding edge in H
As far as I know, this approach is acceptable for solving this problem with non-determinism. My question is this: if we can compare the edges in the permutation of G against H, why can’t we simply check to see if each edge in the original list of edges in G (a maximum of $n^2$ nodes) has a matching edge in H (which also has a maximum of $n^2$ nodes) for a total big O of O($n^4$)? If this is possible, does that mean that this problem is in P?
Asked By : brandaemon
Answered By : D.W.
- Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(c,d)$ from $G$ with $(u,v)$ from $H$. This doesn’t mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched. For instance, trying to simultaneously match both $(a,b)$ and $(c,d)$ to the same edge $(u,v)$ does not correspond to any legal graph isomorphism (different vertices have to map to different vertices, and different edges to different edges).
- Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(b,c)$ from $G$ with $(w,x)$ from $H$, where $v ne w$. This doesn’t mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched. For instance, trying to simultaneously match $(a,b)$ to $(u,v)$ and $(b,c)$ to $(w,x)$ doesn’t work, since you need $b$ to be consistently matched to the same vertex in both (e.g., either to $v$ both times, or to $w$ both times).
For these reasons, your approach will indeed run in polynomial time but will not compute the correct result: there will be some graphs $G,H$ where your algorithm outputs “isomorphic” but where the correct answer is “not isomorphic”. If we try to fix this problem, the naive approach is to try to find all ways to match the set of $n$ vertices in $G$ to a re-ordering of the set of vertices in $H$ (i.e., a matching that simultaneously describes what every vertex in $G$ corresponds to, in $H$). However, there are $n!$ such candidates to try, and $n!$ is exponential in $n$, so this leads to an exponential-time algorithm. It’s a famous open problem whether the graph isomorphism problem is in P or not. See https://en.wikipedia.org/wiki/Graph_isomorphism.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49935
