Title: Computing canonical forms of graphs
Abstract: Determining the computational complexity of the problem of finding canonical representatives of graphs is a long-standing unresolved question. This question is of fundamental interest in the theory of computing because of its close relationship with graph-isomorphism testing.
While the problem may be difficult in general, group-theoretic methods have enabled polynomial-time solutions for important classes of graphs, including graphs of bounded valence. In practice, however, variants of backtrack search to find lexicographic leaders have long been accepted as quite effective; for example, the system nauty is the leader in this category.
In this talk, I will discuss theoretical limitations of the lexicographic-leader approach to finding canonical forms. It turns out that this approach leads to NP-complete problems, even for very restricted classes of graphs for which there are simple polynomial-time solutions by group-theoretic methods.