Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms

Authors Markus Anders, Pascal Schweitzer



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.16.pdf
  • Filesize: 0.76 MB
  • 21 pages

Document Identifiers

Author Details

Markus Anders
  • TU Kaiserslautern, Germany
  • TU Darmstadt, Germany
Pascal Schweitzer
  • TU Kaiserslautern, Germany
  • TU Darmstadt, Germany

Cite AsGet BibTex

Markus Anders and Pascal Schweitzer. Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.16

Abstract

We define a search problem on trees that closely captures the backtracking behavior of all current practical graph isomorphism algorithms. Given two trees with colored leaves, the goal is to find two leaves of matching color, one in each of the trees. The trees are subject to an invariance property which promises that for every pair of leaves of equal color there must be a symmetry (or an isomorphism) that maps one leaf to the other. We describe a randomized algorithm with errors for which the number of visited nodes is quasilinear in the square root of the size of the smaller of the two trees. For inputs of bounded degree, we develop a Las Vegas algorithm with a similar running time. We prove that these results are optimal up to logarithmic factors. For this, we show a lower bound for randomized algorithms on inputs of bounded degree that is the square root of the tree sizes. For inputs of unbounded degree, we show a linear lower bound for Las Vegas algorithms. For deterministic algorithms we can prove a linear bound even for inputs of bounded degree. This shows why randomized algorithms outperform deterministic ones. Our results explain why the randomized "breadth-first with intermixed experimental path" search strategy of the isomorphism tool Traces (Piperno 2008) is often superior to the depth-first search strategy of other tools such as nauty (McKay 1977) or bliss (Junttila, Kaski 2007). However, our algorithm also provides a new traversal strategy, which is theoretically near optimal and which has better worst case behavior than traversal strategies that have previously been used.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • Graph isomorphism
  • Lower bounds

Metrics

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

References

  1. Markus Anders and Pascal Schweitzer. Engineering a fast probabilistic isomorphism test. In ALENEX'21: Proceedings of the Symposium on Algorithm Engineering and Experiments, 2021. to appear. Google Scholar
  2. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897542.
  3. Marek Chrobak and Claire Kenyon-Mathieu. SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News, 37(4):115-126, 2006. URL: https://doi.org/10.1145/1189056.1189078.
  4. Paul T. Darga, Hadi Katebi, Mark Liffiton, Igor L. Markov, and Karem Sakallah. Saucy3. http://vlsicad.eecs.umich.edu/BK/SAUCY/.
  5. Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah, and Igor L. Markov. Exploiting structure in symmetry detection for CNF. In Proceedings of the 41st Annual Design Automation Conference, DAC '04, pages 530-534, New York, NY, USA, 2004. ACM. URL: https://doi.org/10.1145/996566.996712.
  6. Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In ALENEX'07: Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, pages 135-149, New Orleans, USA, 2007. SIAM. Google Scholar
  7. José Luis López-Presa, Antonio Fernández Anta, and Luis N. Chiroque. Conauto2. https://sites.google.com/site/giconauto/.
  8. José Luis López-Presa, Luis F. Chiroque, and Antonio Fernández Anta. Novel techniques to speed up the computation of the automorphism group of a graph. J. Applied Mathematics, 2014:934637:1-934637:15, 2014. URL: https://doi.org/10.1155/2014/934637.
  9. Rudolf Mathon. A note on the graph isomorphism counting problem. Inf. Process. Lett., 8(3):131-132, 1979. URL: https://doi.org/10.1016/0020-0190(79)90004-8.
  10. Brendan D. McKay. Practical graph isomorphism. In 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), pages 45-87, 1981. Google Scholar
  11. Brendan D. McKay and Adolfo Piperno. Nauty and traces user guide. https://cs.anu.edu.au/people/Brendan.McKay/nauty/nug25.pdf.
  12. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60(0):94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  13. A. G. Munford. A note on the uniformity assumption in the birthday problem. Amer. Statist., 31(3):119, 1977. URL: https://doi.org/10.2307/2682958.
  14. Daniel Neuen and Pascal Schweitzer. Benchmark graphs for practical graph isomorphism. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 60:1-60:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.60.
  15. Adolfo Piperno. Search space contraction in canonical labeling of graphs (preliminary version). CoRR, abs/0804.4881, 2008. arXiv. URL: http://arxiv.org/abs/0804.4881.
  16. David J. Rosenbaum. Breaking the n^log n barrier for solvable-group isomorphism. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1054-1073. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.76.
  17. Pascal Schweitzer. Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Phd. thesis, Universität des Saarlandes, Saarbrücken, Germany, 2009. Google Scholar
  18. Stoicho D. Stoichev. New exact and heuristic algorithms for graph automorphism group and graph isomorphism. ACM Journal of Experimental Algorithmics, 24(1):1.15:1-1.15:27, 2019. URL: https://doi.org/10.1145/3333250.
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