Document Open Access Logo

A Characterization of Individualization-Refinement Trees

Authors Markus Anders, Jendrik Brachter, Pascal Schweitzer

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.24.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Markus Anders
  • TU Darmstadt, Germany
Jendrik Brachter
  • TU Darmstadt, Germany
Pascal Schweitzer
  • TU Darmstadt, Germany

Funding

Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (EngageS: grant No. {820148}).

Cite As Get BibTex

Markus Anders, Jendrik Brachter, and Pascal Schweitzer. A Characterization of Individualization-Refinement Trees. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.24

Abstract

Individualization-Refinement (IR) algorithms form the standard method and currently the only practical method for symmetry computations of graphs and combinatorial objects in general. Through backtracking, on each graph an IR-algorithm implicitly creates an IR-tree whose order is the determining factor of the running time of the algorithm.
We give a precise and constructive characterization which trees are IR-trees. This characterization is applicable both when the tree is regarded as an uncolored object but also when regarded as a colored object where vertex colors stem from a node invariant. We also provide a construction that given a tree produces a corresponding graph whenever possible. This provides a constructive proof that our necessary conditions are also sufficient for the characterization.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Trees
Keywords
  • individualization refinement algorithms
  • backtracking trees
  • graph isomorphism

Metrics

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

Related Versions

References

  1. Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 2112-2118. ijcai.org, 2021. URL: https://doi.org/10.24963/ijcai.2021/291.
  2. Markus Anders, Jendrik Brachter, and Pascal Schweitzer. A characterization of individualization-refinement trees. CoRR, abs/2109.07302, 2021. Full version of the paper. URL: http://arxiv.org/abs/2109.07302.
  3. Markus Anders and Pascal Schweitzer. dejavu. URL: https://www.mathematik.tu-darmstadt.de/dejavu.
  4. Markus Anders and Pascal Schweitzer. Engineering a fast probabilistic isomorphism test. In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pages 73-84. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976472.6.
  5. Markus Anders and Pascal Schweitzer. Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms. In ICALP 2021, volume 198 of LIPIcs, pages 16:1-16:21, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.16.
  6. Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The parameterized complexity of fixing number and vertex individualization in graphs. In MFCS2016, volume 58 of LIPIcs, pages 13:1-13:14, 2016. URL: https://doi.org/10.4230/LIPIcs.MFCS.2016.13.
  7. Christoph Berkholz, Paul S. Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory Comput. Syst., 60(4):581-614, 2017. URL: https://doi.org/10.1007/s00224-016-9686-0.
  8. Paul T. Darga, Hadi Katebi, Mark Liffiton, Igor L. Markov, and Karem Sakallah. Saucy3. URL: http://vlsicad.eecs.umich.edu/BK/SAUCY/.
  9. Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah, Igor L. Markov, 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.
  10. Martin Grohe. Equivalence in finite-variable logics is complete for polynomial time. In FOCS '96, pages 264-273. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/SFCS.1996.548485.
  11. Tommi Junttila and Petteri Kaski. bliss. URL: http://www.tcs.hut.fi/Software/bliss/.
  12. Tommi A. Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.13.
  13. José Luis López-Presa, Antonio Fernández Anta, and Luis N. Chiroque. conauto2. URL: https://sites.google.com/site/giconauto/.
  14. José Luis López-Presa, Luis Núñez Chiroque, and Antonio Fernández Anta. Novel techniques for automorphism group computation. In Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings, volume 7933 of LNCS, pages 296-307. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_27.
  15. Brendan D. McKay and Adolfo Piperno. nauty and Traces. URL: http://pallini.di.uniroma1.it.
  16. 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.
  17. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI 2019, pages 4602-4609, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
  18. Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualization-refinement algorithms for graph isomorphism. In STOC 2018, pages 138-150. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188900.
  19. Adolfo Piperno. Search space contraction in canonical labeling of graphs (preliminary version). CoRR, abs/0804.4881, 2008. URL: http://arxiv.org/abs/0804.4881.
  20. Pascal Schweitzer. Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Phd. thesis, Universität des Saarlandes, Germany, 2009. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact