Dynamic Dominating Set in Uniformly Sparse Graphs
2026-07-27 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where you want to quickly keep track of a good-enough set of important nodes (a dominating set) in a graph that changes over time by adding or removing edges. Previous methods depended on a graph’s maximum degree, which can be large, making updates slow. The authors focus instead on a graph property called arboricity, which measures how tree-like or sparse a graph is, and they design an algorithm that updates efficiently based on this property. Their approach works especially well for graphs with low arboricity, achieving fast updates and constant-factor approximations, using a different method called the primal-dual framework rather than earlier greedy techniques.
minimum dominating setdynamic graph algorithmsapproximation algorithmarboricitymaximum degreeprimal-dual frameworkgraph sparsityedge insertions and deletionsupdate timebounded arboricity graphs
Authors
Anton Bukov, Shay Solomon
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(Δ\cdot \log n)$ update time, where $Δ$ 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+ε)\ln Δ$. Is it possible to achieve $\mathrm{poly}(\log n)$ update time without any dependence on $Δ$, for any nontrivial graph family? This basic question has remained open even in {\bf forests} and even for {\bf unweighted instances}. The {\em 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(α\cdot \log (Cn))$, for dynamic graphs whose {\em 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, 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.