Name
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 two-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 nonisomorphic graphs is at most the dimension required to distinguish nonisomorphic 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, Furer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1137/20M1314987 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Weisfeiler-Leman algorithm, separators, first-order logic, counting quantifiers | Conference | 36 |
Issue | ISSN | Citations |
1 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sandra Kiefer | 1 | 9 | 2.50 |
| Daniel Neuen | 2 | 9 | 5.03 |