2026/07/24 by Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk +1
#cs.DS
Let \mathscrC be a class of graphs of bounded expansion and r,k∈ ℕ 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∈ \mathscrC 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 ε, for a parameter ε>0 fixed upon the initialization. The amortized update time is logc n⋅ log (1)/(ε), where n is the vertex count of G and c is a constant that depends only on r, k, and \mathscrC. 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^\cal O(d)⋅ log3 n⋅ log (1)/(ε). Finally, we prove that in graphs of degeneracy at most d, one can maintain an \cal O(d2)-approximation of the minimum size of a (distance-1) dominating set with amortized expected update time d^\cal O(1)⋅ log n.