Distributed ∆-coloring plays hide-and-seek

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 Δ log n ) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework.

Authors

• Alkida Balliu
• Sebastian Brandt 0002
• Fabian Kuhn
• Dennis Olivetti

Keywords

• distributed computing
• round elimination
• maximal independent set
• ruling set
• coloring
• LOCAL model
• lower bounds