Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

We present a deterministic distributed algorithm that computes a (2Δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree Δ, in O(log 8 Δ·log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms} from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e. g. , Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2 O(√(log n) by Panconesi and Srinivasan [STOC'92] and Õ(√(Δ)) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS'16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2Δ-1)-edge-coloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Δ, this algorithm computes a maximal matching in O(r 5 log 6+log r Δ·log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkins book, a ((log Δ/ε) O(log 1/ε) )-round deterministic algorithm for (1+ε)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting λ-arboricity graphs with out-degree at most ⌈(1+ε)λ⌉, for any constant ε>0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.

Authors

• Manuela Fischer
• Mohsen Ghaffari 0001
• Fabian Kuhn

Keywords

• Complexity theory
• Distributed algorithms
• Color
• Partitioning algorithms
• Computer science
• Computational modeling
• Standards
• Maximum Matching
• Independent Set
• Matching Algorithm
• Maximum Degree
• Long-standing Question
• Distributed Algorithm
• Maximal Set
• Distribution Graph
• Maximum Independent Set
• Graph Algorithms
• Factor 2
• Efficient Algorithm
• Estimation Algorithm
• Linear Programming
• Integrable
• Class Of Problems
• Constant Factor
• Fractional Value
• Algorithm For Problem
• Line Graph
• Edge Values
• Approximate Matching
• Graph Matching
• Incident Edges
• Graph Problems
• Polylogarithmic
• Regular Graphs
• Proof Sketch
• Color Categories
• Fractional Solution
• distributed graph algorithms
• local algorithms
• deterministic distributed algorithms
• edge-coloring
• hypergraph
• maximal matching
• rounding linear programs