


























We consider the problem of maintaining a $(1+ε)Δ$-edge coloring in a dynamic graph $G$ with $n$ nodes and maximum degree at most $Δ$. The state-of-the-art update time is $O_ε(\text{polylog}(n))$, by Duan, He and Zhang [SODA'19] and by Christiansen [STOC'23], and more precisely $O(\log^7 n/ε^2)$, where $Δ= Ω(\log^2 n / ε^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 $ε$)? This question coincides with the \emph{static} time barrier for the problem: Even for $(2Δ-1)$-coloring, there is only a naive $O(m \log Δ)$-time algorithm. We answer this fundamental question in the affirmative, by presenting a dynamic $(1+ε)Δ$-edge coloring algorithm with $O(\log^4 (1/ε)/ε^9)$ update time, provided $Δ= Ω_ε(\text{polylog}(n))$. As a corollary, we also get the first linear time (for constant $ε$) \emph{static} algorithm for $(1+ε)Δ$-edge coloring; in particular, we achieve a running time of $O(m \log (1/ε)/ε^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].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。