The power of the Weisfeiler-Leman algorithm to decompose graphs

DOI10.1137/20M1314987MaRDI QIDQ5028356zbMATH OpenFDO

Authors Sandra Kiefer, Daniel Neuen

Publication date 9 February 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programminggraph decompositiongraph isomorphismtime complexityWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The Weisfeiler-Leman procedure is a widely-used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given non-isomorphic graphs is at most the dimension required to distinguish non-isomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for k >= 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of the class of graphs of treewidth at most k. Using a construction by Cai, F"urer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.

Recommendations

• The Weisfeiler-Lehman procedure
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• The Weisfeiler-Leman algorithm and recognition of graph properties
• On the Weisfeiler-Leman dimension of fractional packing

Cites work

• scientific article; zbMATH DE number 997668 (Why is no real title available?)
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• A V log V algorithm for isomorphism of triconnected planar graphs
• An optimal lower bound on the number of variables for graph identification
• Complexity of Finding Embeddings in a k-Tree
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Dividing a Graph into Triconnected Components
• Fixed-point definability and polynomial time on graphs with excluded minors
• Graph isomorphism for unit square graphs
• Graph isomorphism in quasipolynomial time (extended abstract)
• Isomorphism of planar graphs (working paper)
• Logical hierarchies in PTIME
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• On recognizing graphs by numbers of homomorphisms
• On the combinatorial power of the Weisfeiler-Lehman algorithm
• On the connectivity of graphs in association schemes
• PEBBLE GAMES AND LINEAR EQUATIONS
• Positive-instance driven dynamic programming for treewidth
• Practical graph isomorphism. II.
• Sherali-Adams relaxations and indistinguishability in counting logics
• The Power of Counting Logics on Restricted Classes of Finite Structures
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• The connectivity of strongly regular graphs
• The vertex-connectivity of a distance-regular graph
• Treewidth. Computations and approximations
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs

Cited in

(11)

• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Isomorphism testing for embeddable graphs through definability
• On the Weisfeiler-Leman dimension of fractional packing
• The Weisfeiler-Leman algorithm and recognition of graph properties
• The Weisfeiler-Leman dimension of planar graphs is at most 3
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• On WL-rank and WL-dimension of some Deza circulant graphs
• Canonisation and Definability for Graphs of Bounded Rank Width
• The Weisfeiler-Lehman procedure
• On the Power of the Semi-Separated Pair Decomposition
• The Weisfeiler-Leman algorithm and recognition of graph properties

Describes a project that uses

Uses Software

• Traces
• nauty

This page was built for publication: The power of the Weisfeiler-Leman algorithm to decompose graphs

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