Practical graph isomorphism. II.

*(English)*Zbl 1394.05079Summary: We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key implementations. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.

For Part I, see [Numerical mathematics and computing, Proc. 10th Manitoba Conf., Winnipeg/Manitoba 1980, Congr. Numerantium 30, 45–87 (1981; Zbl 0521.05061)].

For Part I, see [Numerical mathematics and computing, Proc. 10th Manitoba Conf., Winnipeg/Manitoba 1980, Congr. Numerantium 30, 45–87 (1981; Zbl 0521.05061)].

##### MSC:

05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |

05C85 | Graph algorithms (graph-theoretic aspects) |

68Q25 | Analysis of algorithms and problem complexity |

##### References:

[1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The design and analysis of computer algorithms, 86, (1974), Addison-Wesley Reading |

[2] | Arlazarov, V. L.; Zuev, I. I.; Uskov, A. V.; Faradzev, I. A., An algorithm for the reduction of finite non-oriented graphs to canonical form, Ž. Vyčisl. Mat. Mat. Fiz., 14, 737-743, (1974) |

[3] | Babai, L.; Kantor, W. M.; Luks, E. M., Computational complexity and the classification of finite simple groups, (Proceedings of the 24th Annual Symposium on the Foundations of Computer Science, (1983)), 162-171 |

[4] | Bodlaender, H., Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 631-643, (1990) |

[5] | Butler, G.; Lam, C. W.H., A general backtrack algorithm for the isomorphism problem of combinatorial objects, J. Symb. Comput., 1, 363-381, (1985) |

[6] | Colbourn, C. S.; Booth, K. S., Linear time automorphism algorithms for trees, interval graphs, and planar graphs, SIAM J. Comput., 10, 203-225, (1981) |

[7] | Corneil, D. G.; Gotlieb, C. C., An efficient algorithm for graph isomorphism, J. ACM, 17, 51-64, (1970) |

[8] | Darga, P. T.; Liffiton, M. H.; Sakallah, K. A.; Markov, I. L., Exploiting structure in symmetry detection for CNF, (Proceedings of the 41st Design Automation Conference, (2004)), 530-534 |

[9] | Darga, P. T.; Sakallah, K. A.; Markov, I. L., Faster symmetry discovery using sparsity of symmetries, (Proceedings of the 45th Design Automation Conference, (2008)), 149-154 |

[10] | Filotti, I. S.; Mayer, J. N., A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, (Proceedings of the 12th ACM Symposium on Theory of Computing, (1980)), 236-243 |

[11] | Foggia, P.; Sansone, C.; Vento, M., A performance comparison of five algorithms for graph isomorphism, (Proceedings of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition, (2001)), 188-199 |

[12] | Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems, J. ACM, 38, 690-728, (1991) |

[13] | Grohe, M., Fixed-point definability and polynomial time on graphs with excluded minors, (Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, (2010)), 179-188 |

[14] | Grohe, M., Structural and logical approaches to the graph isomorphism problem, (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, (2012)), 188 |

[15] | Junttila, T.; Kaski, P., Engineering an efficient canonical labeling tool for large and sparse graphs, (Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, (2007)), 135-149 |

[16] | Junttila, T.; Kaski, P., Conflict propagation and component recursion for canonical labeling, (Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms, (2011)), 151-162 |

[17] | Kawarabayashi, K.; Mohar, B., Graph and map isomorphism and all polyhedral embeddings in linear time, (Proceedings of the 40th Annual ACM symposium on Theory of Computing, (STOCʼ08), (2008)), 471-480 |

[18] | Kirk, A., Efficiency considerations in the canonical labelling of graphs, (1985), Computer Science Department, Australian National University, Technical report TR-CS-85-05 |

[19] | Kocay, W., On writing isomorphism programs, (Wallis, W. D., Computational and Constructive Design Theory, (1996), Kluwer), 135-175 |

[20] | Leon, J. S., Permutation group algorithms based on partitions, I: theory and algorithms, J. Symb. Comput., 43, 545-581, (1990) |

[21] | López-Presa, J. L.; Fernández Anta, A., Fast algorithm for graph isomorphism testing, (Proceedings of the 8th International Symposium on Experimental Algorithms, (2009)), 221-232 |

[22] | López-Presa, J. L.; Fernández Anta, A.; Núñez Chiroque, L., Conauto-2.0: fast isomorphism testing and automorphism group computation, (2011), Preprint. Available at |

[23] | Luks, E., Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci., 25, 42-65, (1982) |

[24] | McKay, B. D., Backtrack programming and isomorph rejection on ordered subsets, Ars Comb., 5, 65-99, (1978) |

[25] | McKay, B. D., Computing automorphisms and canonical labellings of graphs, (Combinatorial Mathematics, Lect. Notes Math., vol. 686, (1978), Springer-Verlag Berlin), 223-232 |

[26] | McKay, B. D., Practical graph isomorphism, Congr. Numer., 30, 45-87, (1980) |

[27] | McKay, B. D.; Piperno, A., , software distribution web page, (2012), and |

[28] | McKay, B. D.; Piperno, A., and userʼs guide (version 2.5), (2012), Available at McKay and Piperno (2012a) |

[29] | Miller, G. L., Isomorphism testing for graphs of bounded genus, (Proceedings of the 12th ACM Symposium on Theory of Computing, (1980)), 225-235 |

[30] | Myrvold, W.; Kocay, W., Errors in graph embedding algorithms, J. Comput. Syst. Sci., 77, 430-438, (2011) |

[31] | Parris, R.; Read, R. C., A coding procedure for graphs, (1969), Univ. of West Indies Computer Centre, Scientific Report. UWI/CC 10 |

[32] | Piperno, A., Search space contraction in canonical labeling of graphs, (2008), Preprint 2008-2011. Available at |

[33] | Ponomarenko, I. N., The isomorphism problem for classes of graphs that are invariant with respec to contraction, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174, 3, 147-177, (1988), (in Russian) |

[34] | Read, R. C.; Corneil, D. G., The graph isomorphism disease, J. Graph Theory, 1, 339-363, (1977) |

[35] | Seress, Á., Permutation group algorithms, (2003), Cambridge University Press Cambridge, x+264 pp |

[36] | Stoichev, S. D., Polynomial time and space exact and heuristic algorithms for determining the generators, orbits and order of the graph automorphism group, (2010), Preprint. Available at |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.