Dynamic Dominating Set in Uniformly Sparse Graphs

Abstract

In the dynamic {\em 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 [HIPS19] it was shown that an $O(\log n)$-approximate MDS can be maintained in {\em unweighted graphs} with $O(\Delta \cdot \log n)$ update time, where $\Delta$ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 [SU23] this was extended to weighted graphs and improves the approximation guarantee to $(1+\epsilon)\ln \Delta$. Is it possible to achieve $\mathrm{poly}(\log n)$ update time without any dependence on $\Delta$, for any nontrivial graph family? This basic question has remained open even in {\bf forests} and even for {\bf unweighted instances}. The {\em arboricity} $\alpha=\alpha(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 $\alpha$ is bounded by $\Delta$ in any graph, various real-world graph families exhibit a significant gap between $\alpha$ and $\Delta$. In this work, we show that one can maintain an $O(\alpha)$-approximate MDS with update time $O(\alpha \cdot \log (Cn))$, for dynamic graphs whose {\em arboricity} is bounded by $\alpha$ throughout the update sequence. This replaces the dependence on $\Delta$ in prior update bounds with $\alpha$, while also improving the approximation guarantee for bounded-arboricity graphs. In particular, for any graph family of constant arboricity, our algorithm gives an $O(1)$-approximation with $O(\log (Cn))$ update time. To achieve this result, our algorithm departs from prior {\em greedy-based} approaches, relying instead on the {\em primal-dual framework} and new structural insights specific to bounded arboricity graphs.