Stable Approximation Algorithms for Dominating Set and Independent Set

Mark de Berg; Arpan Sadhukhan; Frits C.R. Spieksma

doi:10.4230/LIPIcs.APPROX/RANDOM.2023.27

Stable Approximation Algorithms for Dominating Set and Independent Set

Mark de Berg, Arpan Sadhukhan, Frits C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

2 Downloads (Pure)

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.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023
Editors	Nicole Megow, Adam Smith
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	27:1-27:19
Number of pages	19
ISBN (Electronic)	978-3-95977-296-9
DOIs	https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.27
Publication status	Published - 4 Sept 2023
Event	26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 - Atlanta, United States Duration: 11 Sept 2023 → 13 Sept 2023

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	275
ISSN (Print)	1868-8969

Conference

Conference	26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023
Country/Territory	United States
City	Atlanta
Period	11/09/23 → 13/09/23

Funding

Funding MdB, AS, and FS are supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	NETWORKS-024.002.003

Keywords

Dynamic algorithms
approximation algorithms
dominating set
independent set
stability

Access to Document

10.4230/LIPIcs.APPROX/RANDOM.2023.27

pdfFinal published version, 882 KBLicence: CC BY

Cite this

de Berg, M., Sadhukhan, A., & Spieksma, F. C. R. (2023). Stable Approximation Algorithms for Dominating Set and Independent Set. In N. Megow, & A. Smith (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023 (pp. 27:1-27:19). Article 27 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 275). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.27

de Berg, Mark ; Sadhukhan, Arpan ; Spieksma, Frits C.R. / Stable Approximation Algorithms for Dominating Set and Independent Set. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023. editor / Nicole Megow ; Adam Smith. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 27:1-27:19 (Leibniz International Proceedings in Informatics (LIPIcs)).

@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 = "{de Berg}, Mark and Arpan Sadhukhan and Spieksma, {Frits C.R.}",

year = "2023",

month = sep,

day = "4",

doi = "10.4230/LIPIcs.APPROX/RANDOM.2023.27",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "27:1--27:19",

editor = "Nicole Megow and Adam Smith",

booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023",

note = "26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 ; Conference date: 11-09-2023 Through 13-09-2023",

}

de Berg, M , Sadhukhan, A & Spieksma, FCR 2023, Stable Approximation Algorithms for Dominating Set and Independent Set. in N Megow & A Smith (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023., 27, Leibniz International Proceedings in Informatics (LIPIcs), vol. 275, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 27:1-27:19, 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023, Atlanta, United States, 11/09/23. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.27

Stable Approximation Algorithms for Dominating Set and Independent Set. / de Berg, Mark ; Sadhukhan, Arpan ; Spieksma, Frits C.R.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023. ed. / Nicole Megow; Adam Smith. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 27:1-27:19 27 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 275).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Stable Approximation Algorithms for Dominating Set and Independent Set

AU - de Berg, Mark

AU - Sadhukhan, Arpan

AU - Spieksma, Frits C.R.

PY - 2023/9/4

Y1 - 2023/9/4

N2 - 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.

AB - 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.

KW - Dynamic algorithms

KW - approximation algorithms

KW - dominating set

KW - independent set

KW - stability

UR - http://www.scopus.com/inward/record.url?scp=85172032980&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX/RANDOM.2023.27

DO - 10.4230/LIPIcs.APPROX/RANDOM.2023.27

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 27:1-27:19

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023

A2 - Megow, Nicole

A2 - Smith, Adam

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023

Y2 - 11 September 2023 through 13 September 2023

ER -

de Berg M , Sadhukhan A , Spieksma FCR. Stable Approximation Algorithms for Dominating Set and Independent Set. In Megow N, Smith A, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 27:1-27:19. 27. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.APPROX/RANDOM.2023.27

Stable Approximation Algorithms for Dominating Set and Independent Set

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this