Dynamic Edge Coloring of Forests
This work provides tight bounds and optimal algorithms for dynamic edge coloring on forests, a natural restriction of the problem, addressing both deterministic and randomized settings.
This paper studies dynamic edge coloring on forests, aiming to minimize recourse (number of recolorings). For incremental forests, the greedy algorithm achieves O(1/(c+√Δ)) amortized recourse (tight), while for fully dynamic forests, greedy has Ω(log_Δ n) recourse; an optimal non-greedy algorithm achieves O(1) recourse for rooted forests with c=Δ-2. Randomized algorithms achieve Θ(1/Δ) expected recourse incrementally and Θ(min{Δ/c, log_Δ n}) dynamically, optimal for c=0.
In the \emph{dynamic edge coloring} problem, one has to maintain a graph of maximum degree $Δ$ with at most $Δ+c$ colors, given updates to the edges of the graph. An important objective is to minimize the \emph{recourse}, which is the number of edges being recolored. We study this problem on forests, which is a natural yet nontrivial restriction of the problem. We consider the problem in both \emph{incremental} (edges are only inserted) and \emph{fully dynamic} (edges may be deleted) models. In the deterministic setting, we show that the natural greedy algorithm achieves $O(\frac{1}{c + \sqrtΔ})$ amortized recourse in the incremental model, and this is tight up to tie-breaking. In contrast, in a fully dynamic forest, greedy can be forced to have $Ω(\log_Δn)$ amortized recourse. To partially alleviate this limitation of greedy, we show an optimal non-greedy algorithm with $O(1)$ amortized recourse for \emph{rooted} fully dynamic forests and $c = Δ- 2$. In the randomized setting, we give a natural distribution-maintaining algorithm that achieves $Θ(\frac{1}Δ)$ expected amortized recourse in the incremental model and $Θ(\min \{ \fracΔ{c}, \log_Δ n \})$ expected recourse in the dynamic model. These randomized results are optimal for $c=0$.