Stable Approximation Algorithms for Dominating Set and Independent Set
Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma · SIAM Journal on Discrete Mathematics · 2025
Abstract. We study Dominating Set and Independent Set for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is [Formula: see text]- stable when it makes at most [Formula: see text] changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter [Formula: see text] of the algorithm and the approximation ratio it achieves. We obtain the following results: (i) We show that there is a constant [Formula: see text] such that any dynamic [Formula: see text]-approximation algorithm for Dominating Set has stability parameter [Formula: see text], even for bipartite graphs of maximum degree 4. (ii) We present algorithms with very small stability parameters for Dominating Set in the setting where the arrival degree of each vertex is upper bounded by [Formula: see text]. In particular, we give a 1-stable [Formula: see text]-approximation algorithm, a 3-stable [Formula: see text]-approximation algorithm, and an [Formula: see text]-stable [Formula: see text]-approximation algorithm. (iii) We show that there is a constant [Formula: see text] such that any dynamic [Formula: see text]-approximation algorithm for Independent Set has stability parameter [Formula: see text], even for bipartite graphs of maximum degree 3. (iv) Finally, we present a 2-stable [Formula: see text]-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant [Formula: see text] at all times. We extend this latter algorithm to the fully dynamic model where vertices can also be deleted, achieving a 6-stable [Formula: see text]-approximation algorithm.