Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

Abstract

We consider the problem of maintaining a $(1+\epsilon )\Delta$-edge coloring in a dynamic graph $G$ with $n$ nodes and maximum degree at most $\Delta$. The state-of-the-art update time is $O_{\epsilon }(\text{polylog}(n))$, by Duan, He and Zhang [SODA'19] and by Christiansen [STOC'23], and more precisely $O({\log }^{7}n/{\epsilon }^2)$, where $\Delta =\Omega ({\log }^{2}n/{\epsilon }^2)$. The following natural question arises: What is the best possible update time of an algorithm for this task? More specifically, \textbf{ can we bring it all the way down to some constant} (for constant $\epsilon$)? This question coincides with the \emph{static} time barrier for the problem: Even for $(2\Delta -1)$-coloring, there is only a naive $O(m\log \Delta )$-time algorithm. We answer this fundamental question in the affirmative, by presenting a dynamic $(1+\epsilon )\Delta$-edge coloring algorithm with $O({\log }^4(1/\epsilon )/{\epsilon }^9)$ update time, provided $\Delta ={\Omega }_{\epsilon }(\text{polylog}(n))$. As a corollary, we also get the first linear time (for constant $\epsilon$) \emph{static} algorithm for $(1+\epsilon )\Delta$-edge coloring; in particular, we achieve a running time of $O(m\log (1/\epsilon )/{\epsilon }^2)$. We obtain our results by carefully combining a variant of the \textsc{Nibble} algorithm from Bhattacharya, Grandoni and Wajc [SODA'21] with the subsampling technique of Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC'22].

Accepted at SODA 2024