Source-linked AI summary
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Leonid Barenboim, Michael Elkin
TL;DR
Distributed vertex coloring seeks a legal coloring with Δ+1 or slightly more colors in as few communication rounds as possible. The paper uses arbdefective colorings and gives algorithms that trade color count against running time.
Problem
Distributed vertex coloring seeks a legal coloring with Δ+1 or slightly more colors efficiently, a central problem with motivation in real-life network tasks.
Source: §1.1 · p. 2Method
The algorithm partitions graphs into pieces, colors each piece, and unifies the colorings into an arbdefective coloring whose color classes have bounded arboricity.
Source: §1.3 · p. 4Results
O(Δ^{1+η})-coloring in O(log Δ log n) time, Δ^{1+o(1)}-coloring in O(f(Δ) log Δ log n) time, and O(Δ)-coloring in O(Δ^ε log n) time are achieved.
Source: §1.2 · p. 2Takeaways & Limitations
Recursing in parallel on decomposed subgraphs keeps almost all vertices active and is identified as key to the improved running time.
Source: §1.4 · p. 5The stated corollary applies to graphs with arboricity a ≤ Δ^{1−ν} for a constant ν > 0.
Source: §4 · p. 14
Abstract
from arXiv · showhide
Consider an n-vertex graph G = (V,E) of maximum degree Delta, and suppose that each vertex v \in V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in discrete rounds. In the distributed vertex coloring problem the objective is to color G with Delta + 1, or slightly more than Delta + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years \cite{L86, ABI86}. Specifically, these algorithms produce a (Delta + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Delta^2) colors. This algorithm was devised in a seminal FOCS'87 paper by Linial \cite{L87}. Its running time is O(log^* n). In the same paper Linial asked whether one can color with significantly less than Delta^2 colors in deterministic polylogarithmic time. By now this question of Linial became one of the most central long-standing open questions in this area. In this paper we answer this question in the affirmative, and devise a deterministic algorithm that employs \Delta^{1 +o(1)} colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Delta) log Delta log n), for an arbitrarily slow-growing function f(Delta) = \omega(1). We can also produce O(Delta^{1 + \eta})-coloring in O(log Delta log n)-time, for an arbitrarily small constant \eta > 0, and O(Delta)-coloring in O(Delta^{\epsilon} log n) time, for an arbitrarily small constant \epsilon > 0.
1 Introduction
The paper addresses Linial’s long-standing question of whether deterministic polylogarithmic-time coloring can use substantially fewer than O(Δ²) colors. It answers affirmatively with coloring algorithms for bounded arboricity, built around arbdefective colorings and recursive graph decompositions.
1.1 Background and Previous Research
- Deterministic polylogarithmic-time coloring with substantially fewer than O(Δ²) colors was a long-standing open question following Linial’s work.Randomized algorithms already gave (Δ + 1)-coloring in O(log n) time, while the best known deterministic polylogarithmic-time algorithm used O(Δ²) colors.Source: §1.1 · p. 2
1.2 Our Results
- For arbitrarily small η > 0, the paper gives O(Δ^(1+η))-coloring in O(log Δ log n) time, Δ^(1+o(1))-coloring in O(f(Δ) log Δ log n) time, and O(Δ)-coloring in O(Δ^ε log n) time.Here f(Δ) = ω(1) grows arbitrarily slowly, and ε > 0 is arbitrarily small.Source: §1.2 · p. 2
- The results extend to graphs of arboricity at most a, including bounded-genus, bounded-tree-width, and fixed-minor-free graphs; when a ≤ Δ^(1−ν), the algorithm gives (Δ + 1)-coloring in O(log Δ log n) time.The paper also reports deterministic MIS in O(a + a^ε log n) time, improving the state of the art over a stated range of a.Source: §1.2 · p. 3
- For bounded-arboricity graphs, the paper gives O(a²/log^C a)-coloring in O(log log a log n) time and improves prior O(a)-coloring and color-time tradeoffs.It also gives O(a·t)-coloring in O((a·t)^ε log n) time and O(a^(1+η))-coloring in O(log a log n) time, for arbitrarily small positive ε and η.Source: §1.2 · p. 3
1.3 Our Techniques and Overview of the Proof
- An r-arbdefective k-coloring partitions vertices into color classes of arboricity at most r, with rk = O(a), enabling efficient recursive O(a)-coloring.The construction computes an H-partition into O(log n) parts of maximum degree O(a), colors each part defectively, and combines those colorings into an arbdefective coloring.Source: §1.3 · pp. 3–4
1.4 Related Work
- The algorithm recurses in parallel across decomposed subgraphs, unlike prior decomposition schemes that activate only a small portion of vertices in each round.The paper also introduces partial orientations with bounded deficit and length to support efficient arbdefective coloring.Source: §1.3 · p. 4, §1.4 · p. 5
2 Preliminaries
The preliminaries define coloring and orientation concepts used in the paper and summarize distributed tools based on forests decompositions and H-partitions.
2.1 Definitions and Notation
- Orientations are described by length, deficit, and out-degree; legal and defective colorings constrain adjacent vertices and same-colored neighbors, respectively.A legal coloring uses distinct colors across every edge; an m-defective p-coloring permits each vertex at most m same-colored neighbors.Source: §2.1 · p. 5
- An ⌊∆/p⌋-defective O(p^2)-coloring can be computed in O(log* n) time.Source: §2.1 · p. 5
- An r-arbdefective k-coloring uses k colors, with each color class inducing a graph of arboricity at most r.Source: §2.1 · p. 6
2.2 Forests-Decomposition
- An O(a)-forests-decomposition partitions edges into forests, while an H-partition groups vertices into O(log n) sets with bounded later-set neighborhood size.The H-partition degree is ⌊(2 + ǫ) · a⌋ for arbitrarily small positive ǫ.Source: §2.2 · p. 6
- An H-partition supports an acyclic complete orientation with out-degree O(a) in O(log n) time; such an orientation with out-degree k implies arboricity at most k [4, 9].Source: §2.2 · p. 6
3 Small Arboricity Decomposition
The section develops arbdefective colorings through acyclic orientations, then shortens the orientation step using partial orientations. The resulting procedures trade color-class arboricity against runtime.
Simple arbdefective coloring
- Given an acyclic partial orientation of length ℓ, out-degree at most m, and deficit at most τ, Simple-Arbdefective returns a (τ + ⌊m/k⌋)-arbdefective k-coloring in O(ℓ) time.Source: §3 · p. 7
Complete orientations
- Complete-Orientation runs in O(a + log n) time and produces an acyclic orientation with out-degree ⌊(2 + ǫ) · a⌋ and length O(a log n).It uses an H-partition, legally colors each H-set, then orients edges by set index or within-set color order.Source: §3 · p. 8
Simple arbdefective coloring
- An O(a/k)-arbdefective k-coloring can be computed in O(a log n) time by the initial algorithm.Source: §3 · pp. 6, 8
Partial orientations
- Because a complete acyclic orientation can require length Ω(a), the paper instead uses partial orientations with small deficit to obtain shorter paths.Simple-Arbdefective’s runtime is proportional to orientation length.Source: §3 · p. 8
- In O(log n) time, Partial-Orientation produces an acyclic orientation with out-degree ⌊(2 + ǫ) · a⌋, length O(t^2 log n), and deficit at most ⌊a/t⌋.Source: §3 · p. 9
Arbdefective coloring
- An ⌊a/t + (2 + ǫ) · a/k⌋-arbdefective k-coloring is computed in O(t^2 log n) time.Setting t = k gives a ⌊(3 + ǫ) · a/t⌋-arbdefective t-coloring, equivalently a decomposition into t subgraphs of that arboricity.Source: §3 · p. 10
4 Fast Legal Coloring
The section develops legal O(a)-coloring algorithms by refining arbdefective decompositions, trading additional colors for lower running time. Its main bounds range from O(a^µ + (log n)^{1+µ}) time for O(a) colors to polylogarithmic time with a^{1+o(1)} colors.
4 Fast Legal Coloring
- O(a)-coloring via one arbdefective-coloring invocation takes O(a^{2/3} log n) time.The algorithm legally colors each induced color class in parallel and combines the results using disjoint palettes.Source: §4 · p. 11
- Each refinement phase multiplies the number of subgraphs by p and reduces their arboricity by a factor of Θ(p), keeping their product O(a) for a constant number of phases.Once the subgraph arboricities are small enough, parallel legal coloring with distinct palettes yields a unified O(a)-coloring.Source: §4 · pp. 12–13
- O(a)-coloring is computable in O(a^µ log n) time for any positive constant µ < 1.The algorithm repeatedly refines the graph into subgraphs of decreasing arboricity, then legally colors them with distinct palettes.Source: §4 · pp. 12–13
- For graphs with polylogarithmic arboricity in n, O(a)-coloring takes O((log n)^{1+µ′}) time for arbitrarily small constant µ′ > 0.For superlogarithmic arboricity, the stated running-time bound improves to O(a^µ).Source: §4 · pp. 13–14
- O(a)-coloring is computable in O(a^µ + (log n)^{1+µ}) time for any arbitrarily small constant µ > 0.This bound applies to any graph G.Source: §4 · p. 14
- a^{1+o(1)} colors suffice in O(f(a) log a log n) time, where f(a)=ω(1) may grow arbitrarily slowly.The parameters p=k=t=f(a)^{1/2} yield this color-time tradeoff.Source: §4 · p. 14
- O(a^{1+η}) colors suffice in O(log a log n) time for any arbitrarily small constant η > 0.For graphs with a ≤ Δ^{1−ν}, the section also gives a (Δ+1)-coloring in O(log a log n) time.Source: §4 · p. 14
5 Even Faster Coloring
The section accelerates coloring by first constructing arbdefective decompositions, then legally coloring subgraphs or using recoloring to trade colors against time. It gives an O(a²/g(a))-coloring in O(log g(a) log n) time and a separate O(a·t)-coloring tradeoff.
5 Even Faster Coloring
- An (a/t)-arbdefective O(t²)-coloring can be computed in O(log n) time, enabling an O(a·t)-coloring in O((a/t)^µ log n) time.The subgraph colorings are merged with disjoint palettes, and the merging requires no communication.Source: §5 · pp. 15–16
- The Arb-Recolor procedure uses a bounded-outdegree orientation and each vertex’s parent colors to select a new color.The initial orientation has out-degree at most A=(2+ε)·a and is computed in O(log n) time.Source: §5 · p. 15
- The Arb-Kuhn procedure obtains an A/t-arbdefective O(t²)-coloring in O(log* n) time by repeatedly applying Arb-Recolor.Each Arb-Recolor invocation takes O(1) time; here A is the orientation parameter and d=A/t.Source: §5 · p. 15
- O(a²/g(a))-coloring is computable in O(log g(a) log n) time for ω(1)=g(a)=O(a^{1−η}) and arbitrarily small constant η > 0.Taking g(a)=log^c a gives O(a²/log^c a) colors in O(log log a log n) time.Source: §5 · p. 16
A The Length of a Complete Acyclic Orientation
A complete acyclic orientation of length ℓ yields a legal coloring with ℓ+1 colors, so every such orientation has length at least χ(G)−1. The construction colors vertices in rounds after their parents have been colored.
A The Length of a Complete Acyclic Orientation
- A complete acyclic orientation of length ℓ gives a legal (ℓ+1)-coloring, implying its length is at least χ(G)−1.Vertices with equal orientation length cannot be adjacent, and each vertex chooses its color in the round following its length.Source: A The Length of a Complete Acyclic… · p. 18
- The round-based procedure assigns color i to vertices whose parents were colored by round i−1, or earlier.Because each vertex is colored after its parents, adjacent vertices receive different colors.Source: A The Length of a Complete Acyclic… · p. 18
B Proof of Lemma 5.1:
The proof bounds the number of same-colored parents after recoloring by finding an α with few function collisions. A counting contradiction guarantees such an α under Lemma 5.1’s set-size condition.
B Proof of Lemma 5.1:
- If each vertex has an α satisfying the recoloring condition, the resulting coloring has arbdefect at most d and uses at most |A|·|B| colors.For a parent to share the vertex’s new color, both must select the same α and their functions must agree there.Source: B Proof of Lemma 5.1 · p. 18
- The proof seeks an α with at most d−ℓ collisions among differently colored parents, where ℓ parents share the vertex’s original color.Assuming every α has at least d−ℓ+1 such collisions contradicts the bound that each distinct parent color agrees at most k times.Source: B Proof of Lemma 5.1 · pp. 18–19
- The collision-count contradiction violates Lemma 5.1’s condition on |A|, establishing that the required α exists.When A=d, the proof notes that a trivial coloring assigning all vertices the same color has arbdefect d.Source: B Proof of Lemma 5.1 · p. 19