A new filtering algorithm for the graph isomorphism problem

Abstract:

The graph isomorphism problem consists in deciding if two given graphs have an identical structure. This problem may be modeled as a constraint satisfaction problem in a very straightforward way, so that one can use constraint programming to solve it. However, constraint programming is a generic tool that may be less efficient than dedicated algorithms which take advantage of the global semantic of the original problem to reduce the search space.

Hence, we have introduced in [SS04] a global constraint dedicated to graph isomorphism problems, and we have defined a partial consistency ---the label-consistency--- that exploits all edges of the graphs in a global way to narrow variable domains. This filtering algorithm is very powerful in the sense that, for many instances, achieving it allows one to either detect an inconsistency, or reduce variable domains to singletons so that the global consistency can be easily checked. However, achieving the label-consistency implies the computation of the shortest path between every pair of vertices of the graphs, which is rather time consuming.

We propose in this article a new partial consistency for the graph isomorphism problem and an associated filtering algorithm. We experimentally show that this algorithm narrow the variable domains as strongly as our previous label-consistency, but is an order faster, so that it makes constraint programming competitive with {\em Nauty}, the fastest known algorithm for graph isomorphism problem.


Full paper (pdf)