@inproceedings{913c22dd1f1c46158d4033f7ffa8207f,
title = "Stable Approximation Algorithms for Dominating Set and Independent Set.",
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 k-stable when it makes at most k changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter k of the algorithm and the approximation ratio it achieves. We obtain the following results. We show that there is a constant ε ∗ > 0 such that any dynamic (1 + ε ∗)-approximation algorithm for Dominating Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 4. 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 d. In particular, we give a 1-stable (d + 1) 2-approximation, and a 3-stable (9d/2)-approximation algorithm. We show that there is a constant ε ∗ > 0 such that any dynamic (1 + ε ∗)-approximation algorithm for Independent Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 3. Finally, we present a 2-stable O(d)-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant d at all times.",
keywords = "Dynamic algorithms, approximation algorithms, dominating set, independent set, stability",
author = "Berg, {Mark de} and Arpan Sadhukhan and Spieksma, {Frits C. R.}",
note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",
year = "2023",
month = sep,
doi = "10.4230/LIPIcs.APPROX/RANDOM.2023.27",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "27:1--27:19",
editor = "Nicole Megow and Adam Smith",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023",
}