Online Edge Coloring Algorithms via the Nibble Method

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc

Abstract

Nearly thirty years ago, Bar-Noy, Motwani, and Naor [IPL'92] conjectured that an online $(1+o(1))\Delta$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $\Delta=\omega(\log n)$. This conjecture has remained a significant open problem in the field of online algorithms. In this work, we resolve the conjecture in the affirmative for the random-order online model. Furthermore, we investigate edge coloring in the dynamic model with recourse. While previous state-of-the-art results achieved $(1+\epsilon)\Delta$-edge-coloring with $poly(\log n / \epsilon)$ recourse, we provide an algorithm that achieves the same color bound with $poly(1/\epsilon)$ recourse, effectively removing all dependence on the graph size $n$. Both results are derived from a common offline framework based on the Rödl Nibble Method, adapted for the constraints of online and dynamic environments.

Introduction

Edge coloring is a classic problem in combinatorial optimization: the goal is to assign colors to the edges of a graph such that no two incident edges share the same color. Vizing’s Theorem establishes that any graph can be edge-colored using at most $\Delta+1$ colors offline, where $\Delta$ is the maximum degree. However, in the online setting—where edges arrive sequentially and must be colored immediately—the problem becomes significantly more challenging.

A simple greedy approach uses $2\Delta-1$ colors, which is optimal for adversarial arrivals when $\Delta$ is small. However, for graphs with large maximum degrees ($\Delta = \omega(\log n)$), it has long been suspected that a much more efficient coloring is possible. This paper addresses this gap by studying two primary relaxations of the adversarial online model: the random-order online model and the dynamic model with recourse.

The Nibble Method in an Online Context

The technical foundation of our work is the Rödl Nibble Method, a probabilistic technique originally popularized in distributed computing. The method operates in discrete rounds to iteratively color the graph:

  1. Sampling: In each round, a small fraction ($\epsilon$) of currently uncolored edges is selected.
  2. Tentative Coloring: Each sampled edge independently chooses a color at random from its available palette (colors not already finalized by its neighbors).
  3. Conflict Resolution: If two incident edges select the same color, the assignment is discarded, and the edges remain uncolored for the next round. Otherwise, the color is finalized.
  4. Cleanup: After a sufficient number of rounds, the remaining uncolored edges are processed using a greedy algorithm.

Our contribution lies in adapting this offline, multi-round process to online constraints. In the random-order model, we demonstrate that the random arrival sequence of edges naturally mimics the sampling step of the Nibble method. To handle graphs with varying degrees, we utilize a "regularizing gadget"—a virtual expansion involving dummy nodes and edges—to make the graph appear near-regular to the algorithm.

Dynamic Coloring and Recourse

In the dynamic model, edges can be both added and deleted. To maintain a high-quality coloring, algorithms are permitted "recourse"—the ability to re-color a limited number of existing edges. Previous algorithms, such as those by Duan et al. [SODA'19], achieved a $(1+\epsilon)\Delta$-coloring but suffered from a recourse bound that scaled with the number of nodes ($poly(\log n)$).

By applying a distribution-matching technique to our Nibble-based framework, we ensure that the "ripples" caused by an edge update remain local. We prove that the expected recourse is a function of $\epsilon$ alone ($poly(1/\epsilon)$), marking the first time the dependence on $n$ has been eliminated in this context.

Key Results and Analysis

Random-Order Online Model

We settle the Bar-Noy et al. conjecture for the random-order model. For graphs where $\Delta = \omega(\log n)$, our algorithm produces a proper coloring using $\Delta + O(\Delta^\gamma \cdot \log^{1-\gamma} n)$ colors, which is $(1+o(1))\Delta$. We also provide a lower bound showing that if $\Delta = O(\sqrt{\log n})$, even random arrivals may require $2\Delta-2$ colors, suggesting that the $\omega(\log n)$ condition is likely necessary.

Dynamic Model with Recourse

We provide a dynamic algorithm maintaining a $(1+\epsilon)\Delta$-coloring with expected recourse of $poly(1/\epsilon)$. This result is achieved by modifying the standard Nibble method to sample edges independently rather than vertex-centrically, allowing for simpler concentration analysis via Hoeffding bounds.

Conclusion

By bridging the gap between distributed computing techniques and online algorithms, we resolve a long-standing conjecture in the random-order model and optimize recourse bounds in dynamic settings. Future work remains in the strictly adversarial online model, where the inability to "look ahead" at future samples makes the Nibble method difficult to apply directly. Additionally, developing versions of these algorithms that do not require prior knowledge of $\Delta$ remains an open challenge for practical streaming applications.

Summary updated

Abstract

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online $(1+o(1))\Delta$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $\Delta=\omega(\log n)$. This conjecture remains open in general, though it was recently proven for bipartite graphs under \emph{one-sided vertex arrivals} by Cohen et al.~[FOCS'19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model. Our main result is in the \emph{random-order} online model. For this model, known results fall short of the Bar-Noy et al.~conjecture, either in the degree bound [Aggarwal et al.~FOCS'03], or number of colors used [Bahmani et al.~SODA'10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al.~conjecture in the affirmative for this model. Our second result is in the adversarial online (and dynamic) model with \emph{recourse}. A recent algorithm of Duan et al.~[SODA'19] yields a $(1+\epsilon)\Delta$-edge-coloring with poly$(\log n/\epsilon)$ recourse. We achieve the same with poly$(1/\epsilon)$ recourse, thus removing all dependence on $n$. Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the R\"odl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al.~[TCS'98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.
BibTeX
@inproceedings{bhattacharya2021online,
  author = {Sayan Bhattacharya and Fabrizio Grandoni and David Wajc},
  title = {{Online Edge Coloring Algorithms via the Nibble Method}},
  booktitle = {SODA},
  year = {2021},
  url = {https://openreview.net/forum?id=AHks7xNwE2},
}
Figure