Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth

DOI10.1109/LICS.2015.69MaRDI QIDQ4635847zbMATH OpenOpenAlexWikidataFDO

Authors A. Krebs, Oleg Verbitsky

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Descriptive complexity and finite models (68Q19) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Given a connected graph $G$ and its vertex $x$, let $U_x(G)$ denote the universal cover of $G$ obtained by unfolding $G$ into a tree starting from $x$. Let $T=T(n)$ be the minimum number such that, for graphs $G$ and $H$ with at most $n$ vertices each, the isomorphism of $U_x(G)$ and $U_y(H)$ surely follows from the isomorphism of these rooted trees truncated at depth $T$. Motivated by applications in theory of distributed computing, Norris [Discrete Appl. Math. 1995] asks if $T(n)len$. We answer this question in the negative by establishing that $T(n)=(2-o(1))n$. Our solution uses basic tools of finite model theory such as a bisimulation version of the Immerman-Lander 2-pebble counting game. The graphs $G_n$ and $H_n$ we construct to prove the lower bound for $T(n)$ also show some other tight lower bounds. Both having $n$ vertices, $G_n$ and $H_n$ can be distinguished in 2-variable counting logic only with quantifier depth $(1-o(1))n$. It follows that color refinement, the classical procedure used in isomorphism testing and other areas for computing the coarsest equitable partition of a graph, needs $(1-o(1))n$ rounds to achieve color stabilization on each of $G_n$ and $H_n$. Somewhat surprisingly, this number of rounds is not enough for color stabilization on the disjoint union of $G_n$ and $H_n$, where $(2-o(1))n$ rounds are needed.

Recommendations

• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• On the power of color refinement
• Comparing Universal Covers in Polynomial Time
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

Cited in

(14)

• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Graph isomorphism, color refinement, and compactness
• Setting ports in an anonymous network: how to reduce the level of symmetry?
• Graphs identified by logics with counting
• On the power of color refinement
• Lov\'asz Meets Weisfeiler and Leman
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Unfoldings and Coverings of Weighted Graphs
• Weisfeiler-Lehman goes dynamic: an analysis of the expressive power of graph neural networks for attributed and dynamic graphs
• The iteration number of colour refinement
• On the expressibility of the reconstructional color refinement
• On regular trees defined from unfoldings and coverings
• Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
• Canonical labeling of sparse random graphs

This page was built for publication: Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth

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