Distributed \Delta -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 \Delta -coloring on \Delta -regular trees requires \Omega (\log _\Delta n) rounds and any randomized such algorithm requires \Omega (\log _\Delta \log n) rounds. We prove this by showing that a natural relaxation of the \Delta -coloring problem is a fixed point in the round elimination framework. As a first application, we show that our \Delta -coloring lower bound proof directly extends to arbdefective colorings. An arbdefective c -coloring of a graph G=(V,E) is given by a c -coloring of V and an orientation of E , where the arbdefect of a color i is the maximum number of monochromatic outgoing edges of any node of color i . We exactly characterize which variants of the arbdefective coloring problem can be solved in O(f(\Delta) + \log ^*n) rounds, for some function f , and which of them instead require \Omega (\log _\Delta n) rounds for deterministic algorithms and \Omega (\log _\Delta \log n) rounds for randomized ones. As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of \Delta for problems that, in some sense, are much easier than \Delta -coloring, as they can be solved in O(\log ^* n) deterministic rounds in bounded-degree graphs. More specifically, we prove lower bounds as a function of \Delta for a large class of distributed symmetry breaking problems, which can all be solved by a simple sequential greedy algorithm. For example, we obtain novel results for the fundamental problem of computing a (2,\beta) -ruling set, i.e., for computing an independent set S\subseteq V such that every node v\in V is within distance \le \beta of some node in S . We in particular show that \Omega (\beta \Delta ^{1/\beta }) rounds are needed even if initially an O(\Delta) -coloring of the graph is given. With an initial O(\Delta) -coloring, this lower bound is tight and without, it still nearly matches the existing O(\beta \Delta ^{2/(\beta +1)}+\log ^* n) upper bound. The new (2,\beta) -ruling set lower bound is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS ’20]. As a special case of the lower bound, we also obtain a tight linear-in- \Delta lower bound for computing a maximal independent set (MIS) in trees. While such an MIS lower bound was known for general graphs, the best previous MIS lower bounds for trees was \Omega (\log \D