Tuesday, February 26, 2008

Practical Graph Isomorphism

Continuing my efforts to prove I was not just sitting out by the pool in New Zealand, I'll mention a highlight of the talks of Brendan McKay (of the Australian National University). Brendan has written code for graph isomorphism called nauty that works quite well in practice, handling graphs with up to millions of nodes. So while the complexity of the graph isomorphism problem is not known, it can be pretty hard to come up with bad examples that are actually hard to solve. As someone who's happy with good heuristics, I found it quite amusing to watch it in action. (On the other hand, it seems that many of the ideas behind this program are "old" by computer science standards. Are there any competing programs/approaches out there? Seems like a possible research direction. to revisit the algorithm engineering for this problem...)

While settling whether graph isomorphism is in P would certainly be interesting, Brendan pointed out that the question of whether it is in coNP is also quite important. Are there polynomial-sized certificates that can be used to prove that two graphs are not isomorphic? And one can imagine in practice one would like to have some methodology for easily convincing someone that two graphs aren't isomorphic.

As Brendan is a co-editor-in-chief of the Electronic Journal of Combinatorics, we also talked a bit at lunch about electronic journals (in particular the EJC). The EJC continues to grow successfully. (I'm happy to say I've published in it, back in 2004.) Remember to support your electronic journals.

1 comment:

David Molnar said...

One simple thought regarding certificates for non-isomorphism: run Nauty for p(n) steps, p() a polynomial, and take the trace of the run as your "certificate." Worst case, verifying this certificate takes the same time as running Nauty from scratch, but maybe there are speedups. In any case it is polynomial sized, verifiable in polynomial time, and a starting point for further optimization.

Then what does this certificate mean? Well, if Nauty terminated in p(n) steps and output "not isomorphic," then the certificate establishes non-isomorphism. Assuming nauty makes no errors, anyway.

Otherwise if the two graphs _are_ isomorphic, then the certificate establishes that they are isomorphic in a special way that requires more than p(n) steps of nauty to discover. For each p(n) we can then ask whether a pair of such graphs exist. (Of course, if the answer for some polynomial p() is that no such graphs exist, graph isomorphism is in coNP. So this is likely hard to prove in general.)

We can also try to get a handle on how "likely in practice" it is to see such a pair of graphs - for example, we can try to prove a theorem about the proportion of such pairs of graphs under our favorite random graph model. That might be easier than trying to reason about arbitrary graphs. Much easier would be to look at the distribution of nauty solving times and get some evidence that nauty "almost always takes p(n) steps on these type of graphs", but that's at the mercy of the examples chosen of course.

This idea is probably old hat to you and everyone who's thought about it. So I'd be curious to know what has been done to follow it up, if you or other reading this happen to know...