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

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

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

(24)

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

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)