Document Open Access Logo

Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth

Author Daniel Wiebking

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.103.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Daniel Wiebking
  • RWTH Aachen University, Germany

Cite As Get BibTex

Daniel Wiebking. Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 103:1-103:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.103

Abstract

We extend Babai’s quasipolynomial-time graph isomorphism test (STOC 2016) and develop a quasipolynomial-time algorithm for the multiple-coset isomorphism problem. The algorithm for the multiple-coset isomorphism problem allows to exploit graph decompositions of the given input graphs within Babai’s group-theoretic framework.
We use it to develop a graph isomorphism test that runs in time n^polylog(k) where n is the number of vertices and k is the minimum treewidth of the given graphs and polylog(k) is some polynomial in log(k). Our result generalizes Babai’s quasipolynomial-time graph isomorphism test.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Hypergraphs
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Graph isomorphism
  • canonization
  • treewidth
  • hypergraphs

Metrics

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

Related Versions

References

  1. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, 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.
  2. László Babai. Groups, graphs, algorithms: The graph isomorphism problem. In Proc. ICM, pages 3303-3320, 2018. Google Scholar
  3. László Babai. Canonical form for graphs in quasipolynomial time: preliminary report. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 1237-1246, 2019. URL: https://doi.org/10.1145/3313276.3316356.
  4. László Babai and Eugene M. Luks. Canonical labeling of graphs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 171-183, 1983. URL: https://doi.org/10.1145/800061.808746.
  5. Hans L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms, 11(4):631-643, 1990. URL: https://doi.org/10.1016/0196-6774(90)90013-5.
  6. Hans L. Bodlaender, Leizhen Cai, Jianer Chen, Michael R. Fellows, Jan Arne Telle, and Dániel Marx. Open problems in parameterized and exact computation-iwpec 2006. UU-CS, 2006, 2006. Google Scholar
  7. Adam Bouland, Anuj Dawar, and Eryk Kopczynski. On tractable parameterizations of graph isomorphism. In Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings, pages 218-230, 2012. URL: https://doi.org/10.1007/978-3-642-33293-7_21.
  8. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  10. I. S. Filotti and Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus (working paper). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 236-243, 1980. URL: https://doi.org/10.1145/800141.804671.
  11. Martin Grohe. Isomorphism testing for embeddable graphs through definability. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 63-72, 2000. URL: https://doi.org/10.1145/335305.335313.
  12. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput., 44(1):114-159, 2015. URL: https://doi.org/10.1137/120892234.
  13. Martin Grohe, Daniel Neuen, and Pascal Schweitzer. A faster isomorphism test for graphs of small degree. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 89-100, 2018. URL: https://doi.org/10.1109/FOCS.2018.00018.
  14. Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An improved isomorphism test for bounded-tree-width graphs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 67:1-67:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.67.
  15. Harald Andrés Helfgott. Isomorphismes de graphes en temps quasi-polynomial (d'après babai et luks, weisfeiler-leman...), 2017. URL: http://arxiv.org/abs/1701.04372.
  16. John E. Hopcroft and Robert Endre Tarjan. A v² algorithm for determining isomorphism of planar graphs. Inf. Process. Lett., 1(1):32-34, 1971. URL: https://doi.org/10.1016/0020-0190(71)90019-6.
  17. Ken-ichi Kawarabayashi. Graph isomorphism for bounded genus graphs in linear time. CoRR, abs/1511.02460, 2015. URL: http://arxiv.org/abs/1511.02460.
  18. Ken-ichi Kawarabayashi and Bojan Mohar. Graph and map isomorphism and all polyhedral embeddings in linear time. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 471-480, 2008. URL: https://doi.org/10.1145/1374376.1374443.
  19. Stefan Kratsch and Pascal Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. In Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings, pages 81-92, 2010. URL: https://doi.org/10.1007/978-3-642-13731-0_9.
  20. Hanns-Georg Leimer. Optimal decomposition by clique separators. Discrete Mathematics, 113(1-3):99-123, 1993. URL: https://doi.org/10.1016/0012-365X(93)90510-Z.
  21. Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM J. Comput., 46(1):161-189, 2017. URL: https://doi.org/10.1137/140999980.
  22. 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: https://doi.org/10.1016/0022-0000(82)90009-5.
  23. Gary L. Miller. Graph isomorphism, general remarks. J. Comput. Syst. Sci., 18(2):128-142, 1979. URL: https://doi.org/10.1016/0022-0000(79)90043-6.
  24. Gary L. Miller. Isomorphism testing for graphs of bounded genus. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 225-235, 1980. URL: https://doi.org/10.1145/800141.804670.
  25. Gary L. Miller. Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus. Information and Control, 56(1/2):1-20, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80047-3.
  26. Wendy Myrvold and William L. Kocay. Errors in graph embedding algorithms. J. Comput. Syst. Sci., 77(2):430-438, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.002.
  27. Daniel Neuen. Hypergraph isomorphism for groups with restricted composition factors. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (virtual conference), 2020. To appear. Google Scholar
  28. Yota Otachi. Isomorphism for graphs of bounded connected-path-distance-width. In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings, pages 455-464, 2012. URL: https://doi.org/10.1007/978-3-642-35261-4_48.
  29. I. N. Ponomarenko. The isomorphism problem for classes of graphs closed under contraction. Journal of Soviet Mathematics, 55(2):1621-1643, June 1991. URL: https://doi.org/10.1007/BF01098279.
  30. Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest. J. Comb. Theory, Ser. B, 35(1):39-61, 1983. URL: https://doi.org/10.1016/0095-8956(83)90079-5.
  31. Pascal Schweitzer and Daniel Wiebking. A unifying method for the design of algorithms canonizing combinatorial objects. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 1247-1258, 2019. URL: https://doi.org/10.1145/3313276.3316338.
  32. Uwe Schöning. Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci., 37(3):312-323, 1988. URL: https://doi.org/10.1016/0022-0000(88)90010-4.
  33. Ákos Seress. Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2003. URL: https://doi.org/10.1017/CBO9780511546549.
  34. Louis Weinberg. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Transactions on Circuit Theory, 13(2):142-148, 1966. Google Scholar
  35. Daniel Wiebking. Normalizes and permutational isomorphisms in simply-exponential time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 230-238, 2020. URL: https://doi.org/10.1137/1.9781611975994.14.
  36. Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, and Dimitrios M. Thilikos. Isomorphism for graphs of bounded distance width. Algorithmica, 24(2):105-127, 1999. URL: https://doi.org/10.1007/PL00009273.
  37. Viktor N. Zemlyachenko. Canonical numbering of trees. In Proc. Seminar on Comb. Anal. at Moscow State University, page 55, 1970. Google Scholar
  38. Viktor N. Zemlyachenko, Nickolay M. Korneenko, and Regina I. Tyshkevich. Graph isomorphism problem. Journal of Soviet Mathematics, 29(4):1426-1481, 1985. 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