(2022) Distributed ∆Coloring Plays HideandSeek.

Text
document.pdf  Accepted Version Download (1MB)  Preview 
Abstract
We prove several new tight or neartight 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 ccoloring of a graph G=(V,E) is given by a ccoloring 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 boundeddegree 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 linearin∆ 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 