Paper Info
Title
Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
Abstract
Given a connected graph G and its vertex x, let U(G,x) 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(G,x) and U(H,y) 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 the value of T(n) is bounded by n. 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 and H we construct for each n to prove the lower bound for T(n) also show some other tight lower bounds. Both having n vertices, G and H 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 and H. Somewhat surprisingly, this number of rounds is not enough for color stabilization on the disjoint union of G and H, where (2-o(1))n rounds are needed.
Year
DOI
Venue
2015
10.1109/LICS.2015.69
LICS
Keywords
Field
DocType
distributed computing, two-variable logic with counting quantifiers, universal covers of graphs, color refinement
Discrete mathematics,Finite model theory,Combinatorics,Vertex (geometry),Upper and lower bounds,Isomorphism,Partition (number theory),Connectivity,Disjoint union,Mathematics,Bounded function
Conference
ISSN
Citations 
PageRank 
1043-6871
4
0.41
References 
Authors
23
2
Name
Order
Citations
PageRank
Andreas Krebs1218.20
Oleg Verbitsky219127.50