4
$\begingroup$

Here is a recent homework problem of mine:

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:

  1. Check if each graph has the same number of nodes
  2. Non-deterministically arrange the edges of G in a permutation that matches H
  3. 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?

$\endgroup$
  • 1
    $\begingroup$ What's a "matching edge"? $\endgroup$ – Yuval Filmus Nov 24 '15 at 19:57
  • 3
    $\begingroup$ You can't look at an edge in isolation, you would have to "match" all edges simultaneously - or alternatively, all vertices. $\endgroup$ – G. Bach Nov 24 '15 at 20:04
  • 1
    $\begingroup$ as far as anyone knows, "hard" graphs have many vertices with the same # of edges making them "locally indistinguishable", ie "nearly regular" etc although top algorithms use this aspect as much as possible. $\endgroup$ – vzn Nov 24 '15 at 21:04
  • $\begingroup$ You seem to be proposing skipping step 2 and going straight to step 3. In that case, which permutation are you going to use? Step 3 says "corresponding", so you have to establish some correspondence first. $\endgroup$ – immibis Nov 25 '15 at 2:15
  • 1
    $\begingroup$ A simple Google query tells you that GI is not known to be either in P or NP-hard despite having been studied extensively. So it's unlikely that an approach as simple (by "lines of code") as yours is a solution to this open question. $\endgroup$ – Raphael Nov 25 '15 at 9:45
4
$\begingroup$

Your approach sounds intuitively appealing on first glance, but it doesn't work. It's not enough that each edge in $G$ has a matching edge in $H$, when taken one at a time. There has to be a way to provide a single matching (isomorphism) that matches every edge of $G$ to a (different) edge of $H$, in a way that preserves the connectivity.

Examples:

  1. 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).

  2. 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.

$\endgroup$
  • $\begingroup$ It's NP-complete right? So it's a famous open problem in the sense that P=NP is a famous open problem. $\endgroup$ – djechlin Nov 25 '15 at 0:32
  • 1
    $\begingroup$ @djechlin, no, that's not correct. The prevalent belief/expectation/conjecture is that most likely GI is not NP-complete -- see the Wikipedia article I linked to, which states that GI is not known to be NP-complete. $\endgroup$ – D.W. Nov 25 '15 at 0:43
3
$\begingroup$

The best algorithm for graph isomorphism, due to Babai, runs in time $e^{O(\log^C n)}$ for some constant $C > 1$. We don't know any polynomial time algorithm for the problem.

Your algorithm, which you haven't quite specified (what are "matching edges"?), doesn't work. Since you haven't specified it, it is hard to explain why it doesn't work, but similar algorithms have been suggested, and have been proven not to work in polynomial time. The archetypal such algorithm identifies types of vertices, and then tries to match them against one another. The problem is that there are pairs on graphs in which all vertices have the same type, in which case you have to resort to checking all permutations.

$\endgroup$
  • 3
    $\begingroup$ Is the algorithm by Babai through scrutiny yet? $\endgroup$ – G. Bach Nov 24 '15 at 20:03
  • 2
    $\begingroup$ No, he hasn't released it yet. $\endgroup$ – Yuval Filmus Nov 24 '15 at 20:04
  • $\begingroup$ Going off G. Bach's comment and what you said, the idea is that we can check if two graphs are isomorphic only by comparing entire permutations of lists of edges at a time, correct? Hence why the non-deterministic approach of finding a matching permutation and comparing it all at once with the other graph. $\endgroup$ – intcreator Nov 24 '15 at 21:39
  • 2
    $\begingroup$ No, in fact there are better approaches, such as Babai's algorithm, as well as many precursors. $\endgroup$ – Yuval Filmus Nov 24 '15 at 21:53
  • $\begingroup$ I agree with @G.Bach; we should not cite an algorithm that is not even known, let alone peer reviewed. (And then turn around and tell people that merits don't matter in science...) You can make your point without, too: there are sub-exponential-time algorithms. $\endgroup$ – Raphael Nov 25 '15 at 9:46

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.