Benchmark Graphs for Practical Graph Isomorphism

Authors Daniel Neuen, Pascal Schweitzer



PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.60.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Daniel Neuen
Pascal Schweitzer

Cite AsGet BibTex

Daniel Neuen and Pascal Schweitzer. Benchmark Graphs for Practical Graph Isomorphism. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.60

Abstract

The state-of-the-art solvers for the graph isomorphism problem can readily solve generic instances with tens of thousands of vertices. Indeed, experiments show that on inputs without particular combinatorial structure the algorithms scale almost linearly. In fact, it is non-trivial to create challenging instances for such solvers and the number of difficult benchmark graphs available is quite limited. We describe a construction to efficiently generate small instances for the graph isomorphism problem that are difficult or even infeasible for said solvers. Up to this point the only other available instances posing challenges for isomorphism solvers were certain incidence structures of combinatorial objects (such as projective planes, Hadamard matrices, Latin squares, etc.). Experiments show that starting from 1500 vertices our new instances are several orders of magnitude more difficult on comparable input sizes. More importantly, our method is generic and efficient in the sense that one can quickly create many isomorphism instances on a desired number of vertices. In contrast to this, said combinatorial objects are rare and difficult to generate and with the new construction it is possible to generate an abundance of instances of arbitrary size. Our construction hinges on the multipedes of Gurevich and Shelah and the Cai-Fürer-Immerman gadgets that realize a certain abelian automorphism group and have repeatedly played a role in the context of graph isomorphism. Exploring limits, we also explain that there are group theoretic obstructions to generalizing the construction with non-abelian gadgets.
Keywords
  • graph isomorphism
  • benchmark instances
  • practical solvers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In STOC, pages 684-697. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897542.
  2. László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán. The graph isomorphism problem (dagstuhl seminar 15511). Dagstuhl Reports, 5(12):1-17, 2015. URL: http://dx.doi.org/10.4230/DagRep.5.12.1.
  3. László Babai, Paul Erdős, and Stanley M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9(3):628-635, 1980. URL: http://dx.doi.org/10.1137/0209047.
  4. László Babai and Youming Qiao. Polynomial-time isomorphism test for groups with abelian sylow towers. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 453-464. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2012.453.
  5. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
  6. Paolo Codenotti, Hadi Katebi, Karem A. Sakallah, and Igor L. Markov. Conflict analysis and branching heuristics in the search for graph automorphisms. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, November 4-6, 2013, pages 907-914. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/ICTAI.2013.139.
  7. Anuj Dawar and David Richerby. The power of counting logics on restricted classes of finite structures. In CSL, volume 4646 of Lecture Notes in Computer Science, pages 84-98. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74915-8_10.
  8. Yuri Gurevich and Saharon Shelah. On finite rigid structures. J. Symb. Log., 61(2):549-562, 1996. URL: http://dx.doi.org/10.2307/2275675.
  9. Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, pages 135-149. SIAM, 2007. URL: http://dx.doi.org/10.1137/1.9781611972870.13.
  10. Ludek Kucera. Canonical labeling of regular graphs in linear average time. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 271-279. IEEE Computer Society, 1987. URL: http://dx.doi.org/10.1109/SFCS.1987.11.
  11. José Luis López-Presa, Antonio Fernández Anta, and Luis Núñez Chiroque. Conauto-2.0: Fast isomorphism testing and automorphism group computation. CoRR, abs/1108.1060, 2011. URL: https://arxiv.org/abs/1108.1060.
  12. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42-65, 1982. URL: http://dx.doi.org/10.1016/0022-0000(82)90009-5.
  13. Rudolf Mathon. Sample graphs for isomorphism testing. In Proceedings of the ninth Southeastern Conference on Combinatorics, Graph Theory and Computing: Florida Atlanta University, Boca Raton, January 30-February 2, 1978, Congressus Numerantium, 21. Winnipeg: Utilitas Mathematica Publish, 1978. Google Scholar
  14. Brendan D. McKay and Adolfo Piperno. nautytraces software distribution web page. http://cs.anu.edu.au/~bdm/nauty/ and URL: http://pallini.di.uniroma1.it.
  15. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: http://dx.doi.org/10.1016/j.jsc.2013.09.003.
  16. Takunari Miyazaki. The complexity of mckay’s canonical labeling algorithm. In Groups and Computation, volume 28 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 239-256. DIMACS/AMS, 1995. Google Scholar
  17. Daniel Neuen and Pascal Schweitzer. Benchmark graphs for practical graph isomorphism. URL: https://www.lii.rwth-aachen.de/research/95-benchmarks.html.
  18. Daniel Neuen and Pascal Schweitzer. Subgroups of 3-factor direct products, 2016. arXiv:1607.03444. URL: https://arxiv.org/abs/1607.03444.
  19. Daniel Neuen and Pascal Schweitzer. Benchmark graphs for practical graph isomorphism. CoRR, abs/1705.03686, 2017. URL: http://arxiv.org/abs/1705.03686.
  20. Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualization-refinement algorithms for graph isomorphism. CoRR, abs/1705.03283, 2017. URL: http://arxiv.org/abs/1705.03283.
  21. Yota Otachi and Pascal Schweitzer. Reduction techniques for graph isomorphism in the context of width parameters. In SWAT, volume 8503 of Lecture Notes in Computer Science, pages 368-379. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08404-6_32.
  22. Pascal Schweitzer. Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Phd. thesis, Universität des Saarlandes, Saarbrücken, Germany, 2009. Google Scholar
  23. Jacobo Torán. On the hardness of graph isomorphism. SIAM J. Comput., 33(5):1093-1108, 2004. URL: http://dx.doi.org/10.1137/S009753970241096X.
  24. Faried Abu Zaid, Erich Grädel, Martin Grohe, and Wied Pakusa. Choiceless polynomial time on structures with small abelian colour classes. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, volume 8634 of Lecture Notes in Computer Science, pages 50-62. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44522-8_5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail