Towards Optimal Distributed Edge Coloring with Fewer Colors
Manuel Jakob, Yannic Maus, Florian Schager · 2025
Read Towards Optimal Distributed Edge Coloring with Fewer Colors by Manuel Jakob, Yannic Maus, Florian Schager (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13003.txt.
Introduction
Colouring the edges of a network so that no node touches two edges of one colour is a basic task in distributed computing, and one colour fewer changes everything. Manuel Jakob, Yannic Maus, and Florian Schager study that cliff edge in their 2025 paper. With 2Δ−1 colours the job is nearly local; with 2Δ−2 it provably needs global coordination.
The team builds a reduction that turns the harder problem into the easier one in logarithmically many rounds, which is provably the best possible. Plugging in known fast algorithms for the easier problem yields an optimal method for a wide range of graph degrees, and a faster one for general graphs than was known. A randomised version cuts the cost further. The work sharpens the map of which network problems are truly local.
Catalog record
| CREATOR | Manuel Jakob, Yannic Maus, Florian Schager |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-13003
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Optimal Distributed Edge Coloring with Fewer Colors Manuel Jakob, Yannic Maus, Florian Schager Abstract There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while ( 2 Δ − 1 ) (2\Delta-1) -edge coloring—where Δ \Delta is the maximum degree—can be solved in 𝒪 ( log ∗ ( n ) ) \mathcal{O}(\log^{\ast}(n)) rounds on constant-degree graphs, the seemingly minor reduction to ( 2 Δ − 2 ) (2\Delta-2) colors leads to an Ω ( log n ) \Omega(\log n) lower bound [Chang, He, Li, Pettie & Uitto, SODA’18]. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper. As our main contribution we design a deterministic distributed 𝒪 ( log n ) \mathcal{O}(\log n) -round reduction from the ( 2 Δ − 2 ) (2\Delta-2) -edge coloring problem to the much easier ( 2 Δ − 1 ) (2\Delta-1) -edge coloring problem. This reduction is optimal, as the ( 2 Δ − 2 ) (2\Delta-2) -edge coloring problem admits an Ω ( log n ) \Omega(\log n) lower bound that even holds on the class of constant-degree graphs, whereas the 2 Δ − 1 2\Delta-1 -edge coloring problem can be solved in 𝒪 ( log ∗ n ) \mathcal{O}(\log^{\ast}n) rounds. By plugging in the ( 2 Δ − 1 ) (2\Delta-1) -edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC’22] running in 𝒪 ( log 12 Δ + log ∗ n ) \mathcal{O}(\log^{12}\Delta+\log^{\ast}n) rounds, we obtain an optimal runtime of 𝒪 ( log n ) \mathcal{O}(\log n) rounds as long as Δ = 2 𝒪 ( log 1 / 12 n ) \Delta=2^{\mathcal{O}(\log^{1/12}n)} . Previously, such an optimal algorithm was only known for the class of constant-degree graphs [Brandt, Maus, Narayanan, Schager & Uitto, SODA’25]. Furthermore, on general graphs our reduction improves the runtime from 𝒪 ~ ( log 3 n ) \widetilde{\mathcal{O}}(\log^{3}n) to 𝒪 ~ ( log 5 / 3 n ) \widetilde{\mathcal{O}}(\log^{5/3}n) . In addition, we also obtain an optimal 𝒪 ( log log n ) \mathcal{O}(\log\log n) -round randomized reduction of ( 2 Δ − 2 ) (2\Delta-2) -edge coloring to ( 2 Δ − 1 ) (2\Delta-1) -edge coloring. This leads to a 𝒪 ~ ( log 5 / 3 log n ) \widetilde{\mathcal{O}}(\log^{5/3}\log n) -round ( 2 Δ − 2 CLOSE (2\Delta-2 )-edge coloring algorithm, which beats the (very recent) previous state-of-the-art taking 𝒪 ~ ( log 8 / 3 log n ) \widetilde{\mathcal{O}}(\log^{8/3}\log n) rounds from [Bourreau, Brandt & Nolin, STOC’25]. Lastly, we obtain an 𝒪 ( log Δ n ) \mathcal{O}(\log_{\Delta}n) -round reduction from the ( 2 Δ − 1 ) (2\Delta-1) -edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem. TU Graz, [email protected]://orcid.org/0009-0009-0229-0287 TU Graz, [email protected]://orcid.org/0000-0003-4062-6991 TU Graz, [email protected]://orcid.org/0009-0009-3923-051X This research was funded in whole or in part by the Austrian Science Fund (FWF) https://doi.org/10.55776/P36280 , https://doi.org/10.55776/I6915 . For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. ccs Theory of computation Distributed algorithms keywords distributed graph algorithms, edge coloring, \mathsf{LOCAL} model † † runningauthor: M. Jakob, Y. Maus and F. Schager † † copyright: Manuel Jakob, Yannic Maus and Florian Schager 1 Introduction There is a huge difference in the techniques and runtimes of distributed algorithms for locally checkable problems that can be solved by a sequential greedy algorithm and those that cannot. For example, on bounded degree graphs, the former problems have distributed complexity \Theta(\log^{\ast}n) [ 24 , 54 , 60 ] while the latter require at least \Omega(\log n) time [ 17 , 19 ] . Understanding this sharp and potentially wide divide between very locally solvable problems and inherently more global ones remains a central open question in distributed computing. A prime example of this contrast—explained in detail next and forming the main topic of this paper—appears in the edge coloring problem. A k -edge coloring of a graph G=(V,E) is a function \varphi:E\to\{1,\dots,k\} such that no two adjacent edges receive the same color. This problem [ 60 , 25 , 28 , 31 , 4 , 16 ] , but also other greedy problems like (\Delta+1) -vertex coloring, maximal independent set, and maximal matching [ 56 , 1 , 11 , 6 , 20 , 2 , 65 , 43 , 29 , 37 ] , has been extensively studied in the field of distributed computing, particularly in the \mathsf{LOCAL} model. In this model the communication network is abstracted as an undirected graph G=(V,E) . Each vertex hosts a processor that may communicate with its neighbors in synchronous rounds. In one round, each processor may send unbounded-size messages to all its neighbors in G and perform unbounded local computations. The goal is to minimize the number of synchronous rounds until every node outputs (a local part of) the solution. The related \mathsf{CONGEST} model additionally imposes a maximum message size of \mathcal{O}(\log n) bits per message. In order to make progress in many parts of the graph in parallel, many distributed algorithms crucially rely on the property that color choices made by other vertices do not affect the solvability on the remaining graph. While this property is satisfied for k=2\Delta-1 (hence we call this the greedy threshold ), for any k<2\Delta-1 there are partial k -edge colorings that cannot be extended to the entire graph [ 5 ] . On the other hand of the spectrum, it is known that every graph admits a (\Delta+1) -edge coloring by a celebrated result of Vizing [ 69 ] . The intuition that coloring with fewer colors is significantly more challenging—particularly in the distributed setting—is evidenced by strong lower bounds: Any deterministic edge coloring algorithm using less than 2\Delta-1 colors requires at least \Omega(\log_{\Delta}n) rounds, and even randomized algorithms face an \Omega(\log_{\Delta}\log n) -round lower bound [ 17 ] . On trees, where these lower bounds are established, there is even a deterministic algorithm that solves the greedy version of the problem in strongly sublogarithmic time, specifically in \mathcal{O}(\log^{12/13}n) rounds [ 16 ] . On bounded degree graphs, the gap is even larger as the greedy version has deterministic and randomized complexity \Theta(\log^{\ast}n) , yet the lower bounds for algorithms that use fewer colors— \Omega(\log n) deterministic and \Omega(\log\log n) randomized—still apply. Despite these challenges, there has been extensive work on designing increasingly faster deterministic and randomized algorithms for edge coloring with fewer than 2\Delta-1 colors—both in the \mathsf{LOCAL} model [ 12 , 13 , 15 , 17 , 18 , 44 , 49 ] , the more restricted \mathsf{CONGEST} model [ 44 , 47 ] , and in other models such as streaming [ 5 , 23 , 66 ]