Distributed ∆-coloring plays hide-and-seek
Alkida Balliu, Sebastian Brandt, Fabian Kühn, Dennis Olivetti
Abstract
We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a Δ-coloring on Δ-regular trees requires Ω(logΔn) rounds and any randomized such algorithm requires Ω(logΔlogn) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework.
Topics & Concepts
Computer scienceDistributed algorithmRandomized algorithmCombinatoricsGraph coloringDiscrete mathematicsBinary logarithmMathematicsTheoretical computer scienceAlgorithmDistributed computingGraphComplexity and Algorithms in GraphsOptimization and Search ProblemsCryptography and Data Security