TL;DR
This paper presents the first online algorithm to break the "barrier of 2" competitive ratio for edge coloring under adversarial edge arrivals, achieving a ratio of $\frac{e}{e-1} + o(1) \approx 1.58$. The authors achieve this by reducing the problem to matching on locally treelike graphs and employing correlation decay techniques—a staple of statistical physics—to analyze the algorithm's performance.
What Problem Does This Paper Address?
Edge coloring is a fundamental graph theory problem: assign colors to edges such that no two edges sharing a vertex have the same color. Offline, Vizing’s theorem tells us we can do this with at most $\Delta+1$ colors (where $\Delta$ is the maximum degree).
In the online setting, edges arrive one by one, and the algorithm must irrevocably assign a color to each new edge immediately. The "gold standard" for online algorithms is the competitive ratio—the number of colors used by the online algorithm divided by the optimal number of colors needed offline ($\approx \Delta$).
For decades, the best known result for general adversarial edge arrivals was the trivial greedy algorithm, which uses $2\Delta-1$ colors (a ratio of 2). While better results existed for special cases like random arrival orders or vertex-by-vertex arrivals, the general edge-arrival model remained "out of reach." The authors tackle this long-standing challenge, making the first significant progress toward a 30-year-old conjecture by Bar-Noy, Motwani, and Naor that a $1+o(1)$ ratio should be possible.
Methods
The authors' approach is built on three main pillars:
- Reduction to Matching: They use a standard technique that transforms the edge coloring problem into a sequence of online matching problems. If you can consistently find a matching that covers each edge with a certain probability, you can build up a full coloring.
- Subsampling for Local Treelikeness: To solve the matching problem, the algorithm first subsamples the incoming edges. By keeping only a small fraction of edges, they ensure that the resulting graph is "locally treelike"—meaning that for most edges, their immediate neighborhood contains no cycles and looks like a tree.
- Tree Recurrences and Correlation Decay: This is the core technical innovation. On a tree, matching probabilities can be calculated using simple recurrences. The authors argue that even if an adversary controls the "boundary" of a local neighborhood to try and mess up the algorithm, the influence of those boundary decisions decays as you move toward the center of the neighborhood.
To analyze this, they define a witness tree (illustrated in Figure 1), which captures all the edges that could possibly influence whether a specific edge $e$ gets matched.
By proving a monotonicity property, they show that the worst thing an adversary can do is leave all boundary edges unmatched. This simplifies the analysis, allowing them to use tools from statistical physics to prove that the error in matching probability shrinks rapidly as the neighborhood size grows.
Datasets
Not discussed in the paper. As a theoretical work in computer science, the results are proven mathematically for all graphs satisfying the degree requirement ($\Delta = \omega(\log n)$) rather than evaluated on specific empirical datasets.
Key Insights and Ideas
- Breaking the Dual Barrier: Interestingly, for the "dual" problem of online matching, a competitive ratio of 2 is a known hard lower bound. This paper shows that edge coloring is fundamentally different and easier to solve than pure matching in the edge-arrival setting.
- Physics meets Algorithms: The use of "correlation decay" and "Gibbs measures" (concepts from statistical physics) provides a powerful framework for analyzing online uncertainty. It formalizes the intuition that "far away" parts of a graph shouldn't have a huge impact on local decisions.
- The Power of Monotonicity: A major hurdle in adversarial analysis is the sheer number of strategies the adversary could use. The authors' proof that the adversary's optimal strategy is "oblivious" (deciding boundary edges upfront) is a crucial simplification that makes the tree recurrence analysis possible.
Key Results
- New Competitive Ratio: The algorithm achieves a competitive ratio of $\frac{e}{e-1} + o(1) \approx 1.58$ for graphs where the maximum degree $\Delta$ is at least logarithmic in the number of vertices $n$.
- First Improvement in 30 Years: This is the first nontrivial algorithm to beat the greedy ratio of 2 in the general adversarial edge arrival model.
- Random Order Generalization: The authors also provide an alternate, simpler proof for the random-order arrival model, achieving a near-optimal $1+o(1)$ ratio.
Limitations and Future Work
- The $1+o(1)$ Gap: While $1.58$ is a major improvement, it still falls short of the conjectured $1+o(1)$ ratio. The authors suggest that their current "local" algorithm, which only considers two states (matched or unmatched), might be at its theoretical limit.
- Adaptive Adversaries: The results hold against "oblivious" adversaries (who decide the arrival order before the algorithm starts). Extending this to "adaptive" adversaries (who can change the order based on the algorithm's past choices) remains an open problem.
- Non-Monotone Algorithms: To reach the $1+o(1)$ bound, researchers might need algorithms with more than two states. However, these are much harder to analyze because the "monotonicity" property used in this paper might no longer hold, making the correlation decay much harder to prove.
Summary updated