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(\hat{I}”\cdot \log n)$ update time, where $\hat{I}”$ 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+\hat{I}\mu )\ln \hat{I}”$. Is it possible to achieve $\mathrm{poly}(\log n)$ update time without any dependence on $\hat{I}”$, for any nontrivial graph family? This basic question has remained open even in {\bf forests} and even for {\bf unweighted instances}. The {\em arboricity} $\hat{I}\pm =\hat{I}\pm (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 $\hat{I}\pm$ is bounded by $\hat{I}”$ in any graph, various real-world graph families exhibit a significant gap between $\hat{I}\pm$ and $\hat{I}”$. In this work, we show that one can maintain an $O(\hat{I}\pm )$-approximate MDS with update time $O(\hat{I}\pm \cdot \log (Cn))$, for dynamic graphs whose {\em arboricity} is bounded by $\hat{I}\pm$ throughout the update sequence. This replaces the dependence on $\hat{I}”$ in prior update bounds with $\hat{I}\pm$, 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.

ESA'26