The power of the Weisfeiler-Leman algorithm to decompose graphs

DOI10.1137/20M1314987zbMATH Open1493.68273arXiv1908.05268MaRDI QIDQ5028356FDOQ5028356

Authors: Sandra Kiefer, Daniel Neuen 

Publication date: 9 February 2022

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

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.

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

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

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)

Cites Work

• Practical graph isomorphism. II.
• Title not available (Why is that?)
• Complexity of Finding Embeddings in a k-Tree
• Fixed-point definability and polynomial time on graphs with excluded minors
• Treewidth. Computations and approximations
• An optimal lower bound on the number of variables for graph identification
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dividing a Graph into Triconnected Components
• Title not available (Why is that?)
• The vertex-connectivity of a distance-regular graph
• The connectivity of strongly regular graphs
• On the connectivity of graphs in association schemes
• A V log V algorithm for isomorphism of triconnected planar graphs
• Sherali-Adams relaxations and indistinguishability in counting logics
• Graph isomorphism in quasipolynomial time (extended abstract)
• Logical hierarchies in PTIME
• On recognizing graphs by numbers of homomorphisms
• Isomorphism of planar graphs (working paper)
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• The Power of Counting Logics on Restricted Classes of Finite Structures
• Positive-instance driven dynamic programming for treewidth
• PEBBLE GAMES AND LINEAR EQUATIONS
• On the combinatorial power of the Weisfeiler-Lehman algorithm
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• Title not available (Why is that?)
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Graph isomorphism for unit square 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
• Canonisation and Definability for Graphs of Bounded Rank Width
• On WL-rank and WL-dimension of some Deza circulant graphs
• The Weisfeiler-Lehman procedure
• On the Power of the Semi-Separated Pair Decomposition
• The Weisfeiler-Leman algorithm and recognition of graph properties

Uses Software

• nauty
• Traces

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)