Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Canonizing Graphs of Bounded Tree Width in Logspace

Canonizing Graphs of Bounded Tree Width in Logspace 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 by logarithmic-space (logspace) algorithms. 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 class 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Canonizing Graphs of Bounded Tree Width in Logspace

Download PDF
29 pages

Loading next page...
 
/lp/association-for-computing-machinery/canonizing-graphs-of-bounded-tree-width-in-logspace-I9ZgQIG0MZ
Publisher
Association for Computing Machinery
Copyright
Copyright © 2017 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3132720
Publisher site
See Article on Publisher Site

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 by logarithmic-space (logspace) algorithms. 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 class 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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Oct 4, 2017

Keywords: Algorithmic graph theory

References

  • A logspace algorithm for partial 2-tree canonization
    Arvind, Vikraman; Das, Bireswar; Köbler, Johannes
  • The isomorphism problem for -trees is complete for logspace
    Arvind, Vikraman; Das, Bireswar; Köbler, Johannes; Kuhnert, Sebastian
  • Graph isomorphism in quasipolynomial time {extended abstract}
    Babai, László
  • Polynomial algorithms for graph isomorphism and chromatic index on partial -trees
    Bodlaender, Hans L.
  • Does have short interactive proofs? Inf
    Boppana, R. B.; Hastad, J.; Zachos, S.
  • Logspace and algorithms for graph isomorphism for subclasses of bounded tree-width graphs
    Das, Bireswar; Enduri, MuraliKrishna; Reddy, I. Vinod
  • Restricted space algorithms for isomorphism on bounded treewidth graphs
    Das, Bireswar; Torán, Jacobo; Wagner, Fabian
  • Planar graph isomorphism is in log-space
    Datta, Samir; Limaye, Nutan; Nimbhorkar, Prajakta; Thierauf, Thomas; Wagner, Fabian
  • Graph isomorphism for -free and -free graphs is in log-space
    Datta, Samir; Nimbhorka, Prajakta; Thierauf, Thomas; Wagner, Fabian
  • Graph Theory (3rd ed
    Diestel, Reinhard
  • Logspace versions of the theorems of Bodlaender and Courcelle
    Elberfeld, Michael; Jakoby, Andreas; Tantau, Till
  • Embedding and canonizing graphs of bounded genus in logspace
    Elberfeld, Michael; Kawarabayashi, Ken-ichi
  • Canonizing graphs of bounded tree width in logspace
    Elberfeld, Michael; Schweitzer, Pascal
  • A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus
    Filotti, Ion S.; Mayer, Jack N.
  • Isomorphism testing for embeddable graphs through definability
    Grohe, Martin
  • Fixed-point definability and polynomial time on graphs with excluded minors
    Grohe, Martin
  • A simple algorithm for the graph minor decomposition—Logic meets structural graph theory
    Grohe, Martin; Kawarabayashi, Ken-ichi; Reed, Bruce A.
  • Testing graph isomorphism in parallel by playing a game
    Grohe, Martin; Verbitsky, Oleg
  • Linear time algorithm for isomorphism of planar graphs (preliminary report)
    Hopcroft, J. E.; Wong, J. K.
  • Completeness results for graph isomorphism
    Jenner, Birgit; Köbler, Johannes; McKenzie, Pierre; Torán, Jacobo
  • Space-bounded reducibility among combinatorial problems
    Jones, Neil D.
  • Relativization of questions about log space computability
    Ladner, Richard E.; Lynch, Nancy A.
  • Optimal decomposition by clique separators
    Leimer, Hanns-Georg
  • A logspace algorithm for tree canonization (extended abstract)
    Lindell, Steven
  • Fixed-parameter tractable canonization and isomorphism test for graphs of bounded tree width
    Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
  • Fixed-parameter tractable canonization and isomorphism test for graphs of bounded tree width
    Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
  • Isomorphism testing for graphs of bounded genus
    Miller, Gary L.
  • Reduction techniques for graph isomorphism in the context of width parameters
    Otachi, Yota; Schweitzer, Pascal
  • The isomorphism problem for classes of graphs closed under contraction
    Ponomarenko, I. N.
  • Undirected connectivity in log-space
    Reingold, Omer
  • Graph isomorphism is in the low hierarchy
    Schöning, Uwe
  • Word problems requiring exponential time (preliminary report)
    Stockmeyer, L. J.; Meyer, A. R.
  • A V2 algorithm for determining isomorphism of planar graphs
    Tarjan, Robert Endre
  • On the hardness of graph isomorphism
    Torán, Jacobo
  • Introduction to Circuit Complexity: A Uniform Approach
    Vollmer, Heribert
  • Graphs of bounded tree width can be canonized in AC1
    Wagner, Fabian