Suppose you are given two isomorphic graphs $G$ and $H$. Is there an efficient way of defining an isomorphism $\phi:V(G) \to V(H)$ if we already know they are isomorphic? Or is it just a guess and check process?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Deleted my misleading answer referencing the fact that graph isomorphism is in NP. You need a certificate, which could be (e.g.) a permutation matrix that effects the isomorphism. $\endgroup$– Steve HuntsmanCommented May 1, 2010 at 22:42
-
1$\begingroup$ I think both the “complexity-theory” and “algorithms” tags are relevant to this question. $\endgroup$– Antonio E. PorrecaCommented May 2, 2010 at 8:08
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
A meta-answer: knowing that the answer is yes, for any NP search problem (regardless of completeness), does not help much in finding the answer. The reason is that, if you had an algorithm A that found answers within some small known time bound T(n) for yes-instances of size n, but took much longer on no-instances, you could instead run a modified version of algorithm A that runs either until it finds the answer or until time T(n) has elapsed, and then gives up. The modified version is just as fast on yes-instances, but runs correctly within the same time bound on no-instances.
So the "if we already know they are isomorphic" part of your question is close to meaningless.
That said, there are a lot of things one can do other than naive guessing and checking. The known time bounds for arbitrary graphs are exponential in the square root of the number of vertices, much faster than the factorial time you would get for guessing all possible permutations, and there are many classes of graphs for which graph isomorphisms can be found in polynomial time — see Wikipedia on the graph isomorphism problem.
For practical graph isomorphism checking, Victor's suggestion of just downloading and running nauty is a good one.
answered May 1, 2010 at 23:23
$\begingroup$
$\endgroup$
The other answers have treated the case of finite graphs, but there is something interesting to say about infinite graphs as well.
For example, we might consider the case of computable graphs. A graph is computable if it has a computable edge relation on the vertex set of natural numbers. It is quite natural to inquire of isomorphic computable graphs, whether they have a computable isomorphism.
Question. If $G$ and $H$ are computable graphs and isomorphic, must there be a computable isomorphism?
I hope you will find it interesting to learn that the answer is No. To see this, let me describe two isomorphic graphs, which will both be trees of height 2, having infinitely many leaves on level $1$ and infinitely many leaves on level $2$, but no splitting except at the root. On the one hand, we can easily build a computable such graph $G$, by using $0$ as the root, the remaining even numbers as the level $1$ nodes, and giving exactly the multiples of $4$ a successor on level $2$, using the odd numbers. Next, let me describe another computable presentation $H$ of this graph. We again use $0$ as the root and the remaining even numbers $2n$ as the level one nodes. But this time, we give $2n$ a successor, using the $k^{\rm th}$ odd number in the construction, only if program $n$ halts on input $0$ in less than time $k$. The graphs $G$ and $H$ are certainly isomorphic, because of their trivial form, but there can be no computable isomorphism between them, since any isomorphism would have to send the node $2n$ in $H$ either to a multiple of $4$ or not, and this would reveal whether it gets a successor in $G$, which would in turn tells us whether the program $n$ halts or not, solving the halting problem. So there can be no such computable isomorphism. QED
The argument generalizes to oracles. That is, for any Turing degree $d$, there are isomorphic graphs that are computable from oracle $d$, but no isomorphism between them is computable from $d$. Thus, in the infinite case, one answer to your question is that you cannot compute the isomorphism of isomorphic graphs $G$ and $H$ just knowing $G$ and $H$. The isomorphism may simply have a greater Turing degree.
More generally, this article by Csima, Khoussainov and Liu investigates the class of computably categorical graphs, the graphs $G$ that have the property that any two computable presentations of $G$ should be computably isomorphic.
I discuss the issues of computable categoricity in this MO answer, which asked whether there could be equivalence without us being able to calculate it, a question for which the subject of computable model theory provides numerous answers.
And there is more to say when one moves to uncountable graphs...
answered May 2, 2010 at 3:14
$\begingroup$
$\endgroup$
5
It's still an open problem whether or not graph isomorphism is NP complete, though most cognoscenti in the computational complexity believe it is not. You might look at nauty, Brendan McKay's program which can do this (and more) fairly efficiently for even quite large graphs -- http://cs.anu.edu.au/~bdm/nauty/
answered May 1, 2010 at 22:56
-
2$\begingroup$ I should add, that a result of Gene Luks ix.cs.uoregon.edu/~luks/iso.pdf shows that if the graphs are of bounded valence, then there is a polynomial time algorithm (given in the paper) to test for isomorphism. Looking at the dependency on the valence shows that there is an
$O(\exp(\sqrt{n} \log n)$algorithm to test isomorphism, where $n$ is the number of vertices. The fact that this is sub exponential is what leads one to believe that graph isomorphism is not NP hard. $\endgroup$ Commented May 2, 2010 at 0:52 -
1$\begingroup$ There was a study comparing graph isomorphism programs: tinyurl.com/3793mqq You can see that Nauty is often but not always the best. It is also known to be exponential in $n$ in the worst case, while theoretical bounds are exponential in $\sqrt{n}$ as pointed out above. $\endgroup$– Igor PakCommented May 2, 2010 at 3:12
-
$\begingroup$ Igor, Do you know the date of that study? Basically I don't believe the results, especially figure 2, because I've never known nauty to take more than hundredths of a second on any graph with less than a few hundred vertices, and I have looked hard. Interestingly, but although we do not understand why, the very hardest graphs for nauty seem to be those that arise from very regular configurations found in finite geometry - in particular the bipartite incidence graphs of generalized quadrangles seem to give more "difficulty per vertex" than any others we know. $\endgroup$ Commented May 3, 2010 at 1:01
-
$\begingroup$ The paper says that the experiment was run on an 500 MHz Intel Celeron. That suggests that the computer was from 1999 or 2000 en.wikipedia.org/wiki/Pentium_III#Katmai $\endgroup$ Commented May 4, 2010 at 0:02
-
$\begingroup$ Note the exp(n^{1/2}) running time is not enough to believe that Graph Isomorphism isn't NP-complete... for example, Planar Vertex Cover can be solved in exp(n^{1/2}) and it is NP-complete. The primary reason why researchers believe that Graph Isomorphism isn't NP-complete is that if it were, then the polynomial time hierarchy collapses. (I think the wikipedia article should cover this.) $\endgroup$ Commented May 4, 2010 at 0:10
$\begingroup$
$\endgroup$
As David points out, just knowing that the two graphs are isomorphic can't help you produce an isomorphism, as you could have just assumed this in the first place for any input, and then checked whether your algorithm really produces an isomorphism.
However, if you have an algorithm that always solves the decision problem "is G isomorphic to H?" then it can be used to produce an isomorphism between any two graphs that are isomorphic. This is similar to the fact that if you have some method of answering whether a given 3SAT instance is satisfiable, you can use that method to produce a certificate (an assignment of variables that makes the formula true). This property is known as self-reducibility, and is explained in these lecture notes.
