TL;DR
This paper introduces the first deterministic dynamic algorithm that maintains a $(\Delta + O(\alpha))$-edge coloring of a graph in $\tilde{O}(1)$ amortized update time, where $\Delta$ is the maximum degree and $\alpha$ is the arboricity. For graphs with bounded or sublinear arboricity (such as planar graphs, bounded treewidth graphs, or graphs where $\alpha = O(\Delta^{1-\mu})$), this affirmatively answers whether dynamic edge coloring can achieve a sublinear additive approximation to Vizing's bound in polylogarithmic time.
What Problem Does This Paper Address?
In dynamic edge coloring, a graph evolves via a sequence of edge insertions and deletions. The goal is to maintain a valid edge coloring (no two adjacent edges share a color) using as few colors as possible, while spending minimal time (update time) and changing as few edge colors as possible (recourse) per update.
By Vizing's theorem, any static graph can be colored with $\Delta + 1$ colors. In the dynamic setting, maintaining a $(1 + \epsilon)\Delta$-coloring in polylogarithmic update time is well-understood. However, a major open question has been:
Can we maintain a $(\Delta + O(\Delta^{1-\mu}))$-edge coloring in $\tilde{O}(1)$ update time for some constant $\mu > 0$?
This paper resolves this question in the affirmative for any graph family with small arboricity $\alpha$ (specifically, $\alpha = O(\Delta^{1-\mu})$). Arboricity measures a graph's maximum average density across all subgraphs. Many real-world and structured networks—such as planar graphs, social networks, and bounded genus graphs—have low arboricity even when their maximum degree $\Delta$ is very large (e.g., a star graph has $\Delta = n - 1$ but $\alpha = 1$).
Methods
The authors build their algorithm around a dynamic version of the graph "peeling" decomposition:
-
Hierarchical Graph Decompositions: A graph of arboricity $\alpha$ has average degree at most $2\alpha$ in any induced subgraph. By iteratively filtering out vertices with degree exceeding $O(\alpha)$, one obtains an $L$-level peeling decomposition ($L = O(\log n)$) where each vertex has a bounded out-degree in its level. Existing data structures (Bhattacharya et al., STOC 2015) can maintain this decomposition dynamically in $\tilde{O}(1)$ time.
-
Coloring along Directed Edges (Warmup): When inserting an edge $e = (u, v)$ where $u$ is at a lower level than $v$ ($u \prec v$), $u$ has at most $O(\alpha)$ neighbors at its level or above, while $v$ has at most $\Delta$ neighbors total. With a palette of size $\Delta + O(\alpha)$, there is always a free color available in the intersection. If coloring $e$ causes a conflict with an edge at $u$, the conflicting edge is uncolored and recolored recursively. Crucially, the conflict must involve an endpoint at a strictly lower level, guaranteeing termination in at most $L = O(\log n)$ steps.
-
Decomposition Systems for Dynamic $\alpha$ and $\Delta$: In the fully general case, both $\Delta$ and $\alpha$ vary over time. The authors introduce a decomposition system—a collection of $O(\log n)$ parallel decompositions geometrically spaced by powers of $(1 + \epsilon)$. They define a "good edge coloring" invariant based on local degrees and layer indices. Any edge that violates the invariant after an update or layer shift is uncolored and re-inserted using a potential function $\Psi(S)$ to bound amortized recourse.
Datasets
Not applicable. This is a purely theoretical paper; no experimental evaluations, benchmarks, or real-world datasets were used.
Key Insights and Ideas
- Local Sparsity vs. Global Degree: Even when $\Delta \approx n$, edges only need to avoid colors used by the lower-level endpoint's out-edges ($O(\alpha)$ colors) plus the higher-level endpoint's total edges ($\le \Delta$ colors). The "extra" colors beyond $\Delta$ depend purely on $\alpha$, not $\Delta$.
- Cascades Flow Downward: Re-coloring cascades always push conflicts down the hierarchy levels ($i \to i-1$). Because the decomposition height is $O(\log_{1+\epsilon} n)$, the chain reaction is strictly finite.
- Evading Lower Bounds on Partial Coloring Extension: A known lower bound (Chang et al., SODA 2018) shows extending a $(\Delta + c)$-coloring to one uncolored edge can require $\Omega(\frac{\Delta}{c} \log \frac{cn}{\Delta})$ recolorings in general graphs. This paper demonstrates a structural contrast: for arboricity $\alpha$, a $(\Delta + (2+\epsilon)\alpha)$-coloring can be extended by recoloring only $O(\frac{\log n}{\epsilon})$ edges in the worst case.
Key Results
- Full Dynamic Algorithm: Deterministically maintains a $(\Delta + (4 + \epsilon)\alpha)$-edge coloring that dynamically adapts to current values of $\Delta_t$ and $\alpha_t$, achieving:
- Amortized Update Time: $O(\log^5 n \log \Delta / \epsilon^6)$ (or $O(\log^6 n / \epsilon^6)$).
- Amortized Recourse: $O(\log^4 n / \epsilon^5)$ edge recolorings per update.
- Fixed-Parameter Warmup: When upper bounds on $\Delta$ and $\alpha$ are known:
- Amortized Update Time: $O(\log^2 n \log \Delta / \epsilon^2)$.
- Worst-Case Recourse: $O(\log n / \epsilon)$ edge recolorings per update.
Limitations and Future Work
- Amortized vs. Worst-Case Guarantees: While the simplified fixed-parameter algorithm achieves $O(\log n / \epsilon)$ worst-case recourse, the general algorithm with varying $\alpha$ and $\Delta$ provides only amortized guarantees for both runtime and recourse.
- Sublinear Recourse for General Graphs: The results rely heavily on the arboricity parameter $\alpha$. Finding an algorithm with sublinear additive error in $\Delta$ and polylogarithmic update time for arbitrary graphs (where $\alpha \approx \Delta$) remains an outstanding open problem.
Summary updated