Document Open Access Logo

Canonizing Graphs of Bounded Tree Width in Logspace

Authors Michael Elberfeld, Pascal Schweitzer

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.32.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Michael Elberfeld
Pascal Schweitzer

Cite As Get BibTex

Michael Elberfeld and Pascal Schweitzer. Canonizing Graphs of Bounded Tree Width in Logspace. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.32

Abstract

Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized in deterministic logarithmic space (logspace). This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous classes of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.

Subject Classification

Keywords
  • algorithmic graph theory
  • computational complexity
  • graph isomorphism
  • logspace
  • tree width

Metrics

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

References

  1. Vikraman Arvind, Bireswar Das, Johannes Köbler, and Sebastian Kuhnert. The isomorphism problem for k-trees is complete for logspace. Information and Computation, 217:1-11, 2012. URL: http://dx.doi.org/10.1016/j.ic.2012.04.002.
  2. Vikraman Arvind, Bireswar Das, and Johannes Köbler. A logspace algorithm for partial 2-tree canonization. In Proceedings of the 3rd International Computer Science Symposium in Russia (CSR 2008), number 5010 in Lecture Notes in Computer Science, pages 40-51. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-79709-8_8.
  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. R. B. Boppana, J. Hastad, and S. Zachos. Does co-NP have short interactive proofs? Inf. Process. Lett., 25(2):127-132, May 1987. URL: http://dx.doi.org/10.1016/0020-0190(87)90232-8.
  5. Bireswar Das, MuraliKrishna Enduri, and I.Vinod Reddy. Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs. In 9th International Workshop on Algorithms and Computation (WALCOM 2015), volume 8973 of Lecture Notes in Computer Science, pages 329-334. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-15612-5_30.
  6. Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. Information and Computation, 217:71-83, 2012. URL: http://dx.doi.org/10.1016/j.ic.2012.05.003.
  7. Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC 2009), pages 203-214. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.16.
  8. Samir Datta, Prajakta Nimbhorka, Thomas Thierauf, and Fabian Wagner. Graph isomorphism for K_3,3-free and K₅-free graphs is in log-space. In Proceedings of the 29th Annual IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), volume 4 of LIPIcs, pages 145-156. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2314.
  9. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pages 143-152. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
  10. Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pages 383-392, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591865.
  11. Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. CoRR, abs/1506.07810, 2015. URL: http://arxiv.org/abs/1506.07810.
  12. Ion S. Filotti and Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pages 236-243, New York, NY, USA, 1980. ACM. URL: http://dx.doi.org/10.1145/800141.804671.
  13. Martin Grohe. Isomorphism testing for embeddable graphs through definability. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pages 63-72. ACM, 2000. URL: http://dx.doi.org/10.1145/335305.335313.
  14. Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Proceedings of 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), pages 3-14, 2006. URL: http://dx.doi.org/10.1007/11786986_2.
  15. J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the 6th Annual ACM Symposium on Theory of Computing (STOC 1974), pages 172-184, New York, NY, USA, 1974. ACM. URL: http://dx.doi.org/10.1145/800119.803896.
  16. Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán. Completeness results for graph isomorphism. J. Comput. Syst. Sci., 66(3):549-566, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00042-4.
  17. 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.
  18. Steven Lindell. A logspace algorithm for tree canonization (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC 1992), pages 400-404, New York, NY, USA, 1992. ACM. URL: http://dx.doi.org/10.1145/129712.129750.
  19. Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS 2014), pages 186-195. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.28.
  20. Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. CoRR, abs/1404.0818, 2014. URL: http://arxiv.org/abs/1404.0818.
  21. Gary L. Miller. Isomorphism testing for graphs of bounded genus. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pages 225-235, New York, NY, USA, 1980. ACM. URL: http://dx.doi.org/10.1145/800141.804670.
  22. Yota Otachi and Pascal Schweitzer. Reduction techniques for graph isomorphism in the context of width parameters. In Proceddings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), pages 368-379, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08404-6_32.
  23. I. N. Ponomarenko. The isomorphism problem for classes of graphs closed under contraction. Journal of Mathematical Sciences, 55(2):1621-1643, 1991. URL: http://dx.doi.org/10.1007/BF01098279.
  24. Uwe Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312-323, 1988. URL: http://dx.doi.org/10.1016/0022-0000(88)90010-4.
  25. Robert Endre Tarjan. A V² algorithm for determining isomorphism of planar graphs. Information Processing Letters, 1(1):32-34, 1971. URL: http://dx.doi.org/10.1016/0020-0190(71)90019-6.
  26. Jacobo Torán. On the hardness of graph isomorphism. SIAM Journal on Computing, 33(5):1093-1108, 2004. URL: http://dx.doi.org/10.1137/S009753970241096X.
  27. Fabian Wagner. Graphs of bounded treewidth can be canonized in AC¹. In Proceedings of the 6th International Computer Science Symposium in Russia (CSR 2011), number 6651 in Lecture Notes in Computer Science, pages 209-222. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20712-9_16.
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