An Improved Isomorphism Test for Bounded-Tree-Width Graphs

Authors Martin Grohe, Daniel Neuen, Pascal Schweitzer, Daniel Wiebking



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.67.pdf
  • Filesize: 443 kB
  • 14 pages

Document Identifiers

Author Details

Martin Grohe
  • RWTH Aachen University, Aachen, Germany
Daniel Neuen
  • RWTH Aachen University, Aachen, Germany
Pascal Schweitzer
  • Technische Universität Kaiserslautern, Kaiserslautern, Germany
Daniel Wiebking
  • RWTH Aachen University, Aachen, Germany

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.67

Abstract

We give a new fpt algorithm testing isomorphism of n-vertex graphs of tree width k in time 2^{k polylog(k)} poly n, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2^{O(k^5 log k)}poly n. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree width k. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai's algorithm as a black box in one place. We give a second algorithm which, at the price of a slightly worse run time 2^{O(k^2 log k)}poly n, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Graph algorithms
Keywords
  • graph isomorphism
  • graph canonization
  • tree width
  • decompositions

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 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: http://dx.doi.org/10.1145/2897518.2897542.
  2. László Babai and Eugene M. Luks. Canonical labeling of graphs. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 171-183. ACM, 1983. URL: http://dx.doi.org/10.1145/800061.808746.
  3. Hans L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms, 11(4):631-643, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90013-5.
  4. Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 32:1-32:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://www.dagstuhl.de/dagpub/978-3-95977-001-9, URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.32.
  5. 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: http://dx.doi.org/10.1137/120892234.
  6. Martin Grohe, Daniel Neuen, and Pascal Schweitzer. A faster isomorphism test for graphs of small degree. CoRR, abs/1802.04659, 2018. URL: http://arxiv.org/abs/1802.04659.
  7. Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded rank width. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1010-1029. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.66.
  8. Hanns-Georg Leimer. Optimal decomposition by clique separators. Discrete Mathematics, 113(1-3):99-123, 1993. URL: http://dx.doi.org/10.1016/0012-365X(93)90510-Z.
  9. 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: http://dx.doi.org/10.1137/140999980.
  10. 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.
  11. Rudolf Mathon. A note on the graph isomorphism counting problem. Inf. Process. Lett., 8(3):131-132, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90004-8.
  12. Gary L. Miller. Isomorphism testing and canonical forms for k-contractable graphs (A generalization of bounded valence and bounded genus). In Marek Karpinski, editor, Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983, volume 158 of Lecture Notes in Computer Science, pages 310-327. Springer, 1983. URL: http://dx.doi.org/10.1007/3-540-12689-9_114.
  13. Daniel Neuen. Graph isomorphism for unit square graphs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 70:1-70:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16013, URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.70.
  14. Yota Otachi and Pascal Schweitzer. Reduction techniques for graph isomorphism in the context of width parameters. In R. Ravi and Inge Li Gørtz, editors, Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, 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.
  15. Ilia N. Ponomarenko. The isomorphism problem for classes of graphs closed under contraction. Journal of Mathematical Sciences, 55(2):1621-1643, 1991. 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