A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem
Derek Gordon Corneil, David G. Kirkpatrick · SIAM Journal on Computing · 1980
The graph isomorphism problem has received considerable attention due to the many practical applications of the problem and its unresolved complexity status. To deal with practical instances of the problem, a great deal of effort has gone into the development of seemingly quite effective heuristic algorithms Typically, these algorithms exploit various vertex properties which are invariant under isomorphism.Empirically, these heuristics have been analyzed extensively; however, very little theoretical analysis has been done on their intrinsic value. In this paper we show that most commonly used vertex invariants are theoretically ineffective in the sense that any pair of graphs may be uniquely represented by a pair of graphs where the vertex invariant fails to give any information whatsoever about isomorphism or nonisomorphism. As a byproduct of these results, new restricted families of graphs are shown to be isomorphism complete (i.e., the isomorphism problem on these graphs is polynomial-time equivalent to the general isomorphism problem).