(2022) Distributed ∆-Coloring Plays Hide-and-Seek.
|
Text
document.pdf - Accepted Version Download (1MB) | Preview |
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 Omega(log_∆ n) rounds and any randomized such algorithm requires Omega(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 Omega(log_∆ n) rounds for deterministic algorithms and Omega(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 Omega(β∆^{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 Omega(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 ∆ also imply substantial lower bounds as a function of n. For instance, we obtain that the maximal independent set problem, on trees, requires Omega(log n / log log n) rounds for deterministic algorithms, which is tight.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Sebastian Brandt (SB) |
| Conference: | STOC ACM Symposium on Theory of Computing |
| Depositing User: | Sebastian Brandt |
| Date Deposited: | 28 Feb 2022 08:57 |
| Last Modified: | 28 Feb 2022 08:57 |
| Primary Research Area: | NRA2: Reliable Security Guarantees |
| URI: | https://publications.cispa.saarland/id/eprint/3577 |
Actions
Actions (login required)
 |
View Item |