Timeline for Efficient way of determining isomorphism
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2010 at 0:10 | comment | added | Ryan Williams | 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.) | |
| May 4, 2010 at 0:02 | comment | added | David E Speyer | 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 | |
| May 3, 2010 at 1:01 | comment | added | Gordon Royle | 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. | |
| May 2, 2010 at 3:12 | comment | added | Igor Pak | 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. | |
| May 2, 2010 at 0:52 | comment | added | Victor Miller |
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.
|
|
| May 1, 2010 at 22:56 | history | answered | Victor Miller | CC BY-SA 2.5 |