In this paper, we consider a class of graphs with bounded expansion $\text{C}$, along with fixed natural numbers $r$ and $k$. We present a dynamic data structure that operates on a dynamic graph $G$, allowing edge insertions and deletions while ensuring that $G \text{ belongs to } \text{C}$ at all times. The data structure efficiently maintains answers to the following two queries:
- Does the graph $G$ contain a distance-$r$ dominating set of size $k$?
- Does the graph $G$ contain a distance-$r$ independent set of size $k$?
The data structure is randomized with error probability bounded by $\text{ε}$, where $\text{ε}$ is a fixed parameter upon initialization. The amortized update time is $O(\log^c n \times \log \frac{1}{\text{ε}})$, where $n$ is the number of vertices in $G$, and $c$ is a constant depending only on $r$, $k$, and $\text{C}$. For the first query, the data structure can also output a distance-$r$ dominating set of size $k$, if it exists.
We further prove that when $r=1$, our data structure for the dominating set query can be implemented even under the assumption that the maintained graph $G$ has degeneracy bounded by a constant $d$, resulting in a simpler data structure with improved amortized update time of $O(2^{k^{\text{O}(d)}} \times \log^3 n \times \log \frac{1}{\text{ε}})$. Finally, we demonstrate that in graphs with degeneracy at most $d$, one can maintain an $O(d^2)$-approximation of the minimum size of a (distance-$1$) dominating set with amortized expected update time of $O(d^{\text{O}(1)} \times \log n)$.
Blogger's Review: The dynamic data structure proposed in this paper holds significant theoretical value for domination and independence problems in sparse graphs, particularly in practical applications where it can effectively handle dynamically changing graph structures while providing efficient query and update performance.