License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.27
URN: urn:nbn:de:0030-drops-188527
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18852/
Go to the corresponding LIPIcs Volume Portal

de Berg, Mark ; Sadhukhan, Arpan ; Spieksma, Frits

Stable Approximation Algorithms for Dominating Set and Independent Set

pdf-format:
LIPIcs-APPROX27.pdf (0.9 MB)

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)²-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.

BibTeX - Entry

@InProceedings{deberg_et_al:LIPIcs.APPROX/RANDOM.2023.27,
  author =	{de Berg, Mark and Sadhukhan, Arpan and Spieksma, Frits},
  title =	{{Stable Approximation Algorithms for Dominating Set and Independent Set}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18852},
  URN =		{urn:nbn:de:0030-drops-188527},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.27},
  annote =	{Keywords: Dynamic algorithms, approximation algorithms, stability, dominating set, independent set}
}

Keywords: Dynamic algorithms, approximation algorithms, stability, dominating set, independent set
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI