2026/06/16 by Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
paper · doi:10.1145/3819817
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. As a first application, we show that our Δ -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(Δ) + log ^*n) rounds, for some function f , and which of them instead require Ω (log Δ n) rounds for deterministic algorithms and Ω (log Δ 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 Δ for problems that, in some sense, are much easier than Δ -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,β) -ruling set, i.e., for computing an independent set S⊆ V such that every node v∈ V is within distance ≤ β of some node in S . We in particular show that Ω (β Δ 1/β ) rounds are needed even if initially an O(Δ) -coloring of the graph is given. With an initial O(Δ) -coloring, this lower bound is tight and without, it still nearly matches the existing O(β Δ 2/(β +1)+log ^* n) upper bound. The new (2,β) -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 Ω (log \D