Deterministic Online Bipartite Edge Coloring

We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. e trivial greedy algorithm is (2o(1))-competitive, which is optimal for graphs of low maximum degree, ∆ = O(log n) [BNMN IPL'92]. Numerous online edge-coloring algorithms outperforming the greedy algorithm in various se ings were designed over the years (e.g., [AGKM FOCS'03, BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22, BSVW STOC'24]), all crucially relying on randomization. A commonly-held belief, first stated by [BNMN IPL'92], is that randomization is necessary to outperform greedy.

Surprisingly, we refute this belief, by presenting a deterministic algorithm that beats greedy for sufficiently large ∆ = Ω(log n), and in particular has competitive ratio e e-1 + o(1) for all ∆ = ω(log n). We obtain our result via a new and surprisingly simple randomized algorithm that works against adaptive adversaries (as opposed to oblivious adversaries assumed by prior work), which implies the existence of a similarly-competitive deterministic algorithm [BDBKTW STOC '90]. is is the first use of contention resolution schemes, which are randomized algorithms for randomized inputs, that yields a deterministic algorithm for deterministic se ings.