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 Delta-coloring on.-regular trees requires Omega( log(Delta) n) rounds and any randomized such algorithm requires Omega( log(Delta) logn) 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.-coloring lower bound proof directly extends to arbdefective colorings. An arbdefective Delta-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.. is the maximum number of monochromatic outgoing edges of any node of color... We exactly characterize which variants of the arbdefective coloring problem can be solved in O (f (Delta)+log*n) rounds, for some function.., and which of them instead require Omega(log(Delta)n) rounds for deterministic algorithms and Omega(log(Delta) logn) 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. 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. 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 subset of V such that every node upsilon is an element of V is within distance <= 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-. 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 O( log.). Our lower bound even applies to a much more general family of problems that allows for almost arbitrary combinations of natural constraints from coloring problems, orientation problems, and independent set problems, and provides a single unified proof for known and new lower bound results for these types of problems. All of our lower bounds as a function of Delta also imply substantial lower bounds as a function of n. For instance, we obtain that the maximal independent set problem, on trees, requires Omega( logn/log logn) rounds for deterministic algorithms, which is tight.