Testing Graph Isomorphism in Parallel by Playing a Game

DOI10.1007/11786986_2MaRDI QIDQ3613744zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Oleg Verbitsky

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0603054

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Abstract: Our starting point is the observation that if graphs in a class C have low descriptive complexity in first order logic, then the isomorphism problem for C is solvable by a fast parallel algorithm (essentially, by a simple combinatorial algorithm known as the multidimensional Weisfeiler-Lehman algorithm). Using this approach, we prove that isomorphism of graphs of bounded treewidth is testable in TC1, answering an open question posed by Chandrasekharan. Furthermore, we obtain an AC1 algorithm for testing isomorphism of rotation systems (combinatorial specifications of graph embeddings). The AC1 upper bound was known before, but the fact that this bound can be achieved by the simple Weisfeiler-Lehman algorithm is new. Combined with other known results, it also yields a new AC1 isomorphism algorithm for planar graphs.

Recommendations

• Isomorphism testing for embeddable graphs through definability
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• Graphs of bounded treewidth can be canonized in AC^1
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Fixed-point definability and polynomial time on graphs with excluded minors

Cited in

(25)

• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Graphs of bounded treewidth can be canonized in AC^1
• Isomorphism testing for embeddable graphs through definability
• A Logspace Algorithm for Partial 2-Tree Canonization
• From Invariants to Canonization in Parallel
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• scientific article; zbMATH DE number 4060741 (Why is no real title available?)
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• The Space Complexity of k-Tree Isomorphism
• On the complexity of identifying strongly regular graphs
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Count-free Weisfeiler-Leman and group isomorphism
• Combinatorial refinement on circulant graphs
• The iteration number of colour refinement
• On the descriptive complexity of groups without abelian normal subgroups
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
• The iteration number of the Weisfeiler-Leman algorithm
• The isomorphism problem for \(k\)-trees is complete for logspace
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Logarithmic Weisfeiler-Leman identifies all planar graphs
• Parallel complexity of identifying groups and quasigroups via decompositions

This page was built for publication: Testing Graph Isomorphism in Parallel by Playing a Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613744)