Attacks On Difficult Instances Of Graph Isomorphism: Sequential And Parallel Algorithms (2009)
Link: https://stars.library.ucf.edu/etd/4004/
Abstract: The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative–an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty’s improved descendants). We analyze Miyazaki’s construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time–thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.
This is the thesis for a canonization algorithm called nishe (backup available on GitHub by the original author). The algorithm supports directed edges and vertex colouring, but no edge labels and by extension no multigraphs (seems to use adjacency matrices). The paper containts some good note on the design of canonization algorithms and heavily references nauty, bliss and saucy.
The proposed algorithm is designed in response to a weakness in existing algorithms like nauty, bliss and saucy, which are all based on the individualization refinement paradigm originally by Brendan McKay (nauty). The weakness in these algorithms being a bad choice of starting vertex for Miyazaki graphs.
We analyze Miyazaki’s construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative.This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years).
Canonical form example
As an example of a canonical form, take the minimum graph of all those in its isomorphism class: if graphs are ordered by first taking the adjacency matrix, concatenating its rows together from top to bottom and treating this as an n2-bit binary number, then the minimum graph is the one corresponding to the smallest n2-bit binary number.