2014/07/11 by Andreas Krebs, Krebs, Andreas, Oleg Verbitsky +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Graph theory and applications #Logic in Computer Science (cs.LO) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1407.3175
openalex publication_date 2014/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a connected graph G and its vertex x, let Ux(G) denote the\nuniversal cover of G obtained by unfolding G into a tree starting from x.\nLet T=T(n) be the minimum number such that, for graphs G and H with at\nmost n vertices each, the isomorphism of Ux(G) and Uy(H) surely follows\nfrom the isomorphism of these rooted trees truncated at depth T. Motivated by\napplications in theory of distributed computing, Norris [Discrete Appl. Math.\n1995] asks if T(n)\≤ n. We answer this question in the negative by\nestablishing that T(n)=(2-o(1))n. Our solution uses basic tools of finite\nmodel theory such as a bisimulation version of the Immerman-Lander 2-pebble\ncounting game.\n The graphs Gn and Hn we construct to prove the lower bound for T(n)\nalso show some other tight lower bounds. Both having n vertices, Gn and\nHn can be distinguished in 2-variable counting logic only with quantifier\ndepth (1-o(1))n. It follows that color refinement, the classical procedure\nused in isomorphism testing and other areas for computing the coarsest\nequitable partition of a graph, needs (1-o(1))n rounds to achieve color\nstabilization on each of Gn and Hn. Somewhat surprisingly, this number of\nrounds is not enough for color stabilization on the disjoint union of Gn and\nHn, where (2-o(1))n rounds are needed.\n