Search Results

In the dynamic minimum dominating set (MDS) problem, the goal is to efficiently maintain an approximate MDS in an n-vertex graph with vertex costs in [1/C,1] undergoing edge insertions and deletions. In STACS'19 [Niklas Hjuler et al., 2019] it was shown that an O(log n)-approximate MDS can be maintained in unweighted graphs with O(Δ ⋅ log n) update time, where Δ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 [Solomon and Uzrad, 2023] this was extended to weighted graphs and improves the approximation guarantee to (1+ε)ln Δ. Is it possible to achieve poly(log n) update time without any dependence on Δ, for any nontrivial graph family? This basic question has remained open even in forests and even for unweighted instances. The arboricity α = α(G) of a graph G is the minimum number of edge-disjoint forests whose union is G, and is a standard measure of sparsity. While α is bounded by Δ in any graph, various real-world graph families exhibit a significant gap between α and Δ. In this work, we show that one can maintain an O(α)-approximate MDS with update time O(α⋅log(Cn)), for dynamic graphs whose arboricity is bounded by α throughout the update sequence. This replaces the dependence on Δ in prior update bounds with α, while also improving the approximation guarantee for bounded-arboricity graphs. In particular, for any graph family of constant arboricity, such as planar graphs, bounded treewidth graphs, and more generally graphs excluding a fixed minor, our algorithm gives an O(1)-approximation with O(log (Cn)) update time. To achieve this result, our algorithm departs from prior greedy-based approaches, relying instead on the primal-dual framework and new structural insights specific to bounded arboricity graphs.