Dynamic domination and independence in sparse graphs

Abstract

Let $\mathcal{C}$ be a class of graphs of bounded expansion and $r,k\in \mathbb{N}$ be fixed. We give a dynamic data structure that for a given dynamic graph $G$, updated by edge insertions and deletions subject to the promise that $G\in \mathcal{C}$ at all times, maintains the answer to the following two queries: (a) Does $G$ contain a distance-$r$ dominating set of size $k$? (b) Does $G$ contain a distance-$r$ independent set of size $k$? The data structure is randomized with error probability bounded by $\epsilon$, for a parameter $\epsilon >0$ fixed upon the initialization. The amortized update time is ${\log }^{c}n\cdot \log \frac{1}{\epsilon }$, where $n$ is the vertex count of $G$ and $c$ is a constant that depends only on $r$, $k$, and $\mathcal{C}$. In the case of the first query, the data structure can also output a distance-$r$ dominating set of size $k$, if existent. We also prove that when $r=1$, our data structure for the dominating set query can be implemented even if we only assume that the maintained graph $G$ has degeneracy bounded by a constant $d$, yielding a simpler data structure with an improved amortized update time of $2^{k^{\mathcal{O}(d)}}\cdot {\log }^{3}n\cdot \log \frac{1}{\epsilon }$. Finally, we prove that in graphs of degeneracy at most $d$, one can maintain an $\mathcal{O}(d^2)$-approximation of the minimum size of a (distance-$1$) dominating set with amortized expected update time $d^{\mathcal{O}(1)}\cdot \log n$.

58 pages