Abstract
This paper presents the first online algorithm to break the competitive ratio of 2 for edge coloring under general edge arrivals. By combining a clever subsampling technique that makes graphs look locally like trees with a "correlation decay" analysis from statistical physics, the authors achieve a competitive ratio of approximately 1.58 ($e/(e-1)$). This work makes significant progress on a 30-year-old conjecture in the field of online algorithms.
Introduction
Edge coloring is a classic problem in graph theory: assign colors to the edges of a graph such that no two edges sharing a vertex have the same color. While Vizing’s Theorem establishes that this can be done offline with $\Delta+1$ colors (where $\Delta$ is the maximum degree), the online version is significantly more challenging.
In the online setting, edges arrive sequentially, and the algorithm must irrevocably assign a color to each edge immediately upon arrival. For decades, the best known approach for general edge arrivals was the "greedy" algorithm, which uses up to $2\Delta - 1$ colors—a competitive ratio of 2. Beating this ratio has been a major open challenge since 1992, particularly under the "oblivious adversary" model where the arrival order is fixed in advance but can be arbitrarily difficult.
Methodology
The authors' approach relies on three main pillars to overcome the limitations of greedy coloring:
- Reduction to Matching: The edge coloring problem is reduced to a series of online matching problems. By finding a way to match an edge with a specific probability, a full coloring can be constructed over time.
- Subsampling for "Local Treelikeness": A core difficulty in online matching is that the availability of two endpoints of an edge is correlated. To simplify this, the authors subsample the graph. They demonstrate that if edges are selected with a sufficiently low probability, the neighborhood of any given edge is very likely to be a tree.
- Correlation Decay and Tree Recurrences: While real graphs are not perfect trees, the authors use "correlation decay"—a technique often used in statistical physics—to prove that the influence of distant cycles on an edge's matching probability vanishes quickly.
As illustrated in the figure above, the algorithm analyzes a local tree $W(T)$ around an edge $e=(u,v)$. They use "tree recurrences" to bound the error introduced by the adversary's choices at the boundaries ($\partial T$) of these local trees. By defining an "Edge Matching Game," they prove a monotonicity property: the worst-case scenario for an adversary trying to prevent an edge from being matched is to leave all boundary edges unmatched. This simplifies the analysis from a complex game-theoretic battle to a manageable recursive calculation.
Key Results
- Breaking the Barrier: The algorithm achieves a competitive ratio of $\frac{e}{e-1} + o(1) \approx 1.58$, a significant improvement over the greedy ratio of 2.0.
- Random Order Improvement: The paper provides a new proof for the "random-order" arrival model, showing that a ratio of $1 + o(1)$ is achievable when edges arrive in a shuffled order rather than a worst-case order.
- Efficiency: The algorithm is computationally efficient, running in $\tilde{O}(1)$ time per edge using standard data structures.
Discussion and Future Work
The specific constant $e/(e-1)$ arises naturally from the limit of the tree recurrences, representing the threshold where errors in the probability calculation stop magnifying and start contracting. While this work breaks the ratio of 2 for oblivious adversaries, it remains an open question whether this can be achieved against an adaptive adversary who sees the algorithm's previous random choices.
Furthermore, the authors believe the original 1992 conjecture—that a $1+o(1)$ ratio is possible even for adversarial arrivals—is true. This paper provides a framework that gets halfway there, suggesting that future "local" algorithms with more complex states might finally reach the optimal bound.
Summary updated