Sidestepping Barriers for Dominating Set in Parameterized Complexity

Ioannis Koutis; Michał Włodarczyk; Meirav Zehavi

doi:10.4230/LIPIcs.IPEC.2023.31

Sidestepping Barriers for Dominating Set in Parameterized Complexity

Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the classic Dominating Set problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters treewidth, vertex modulator to constant treewidth and solution size; (iv,v) FPT-algorithms for the parameters vertex cover number and feedback edge set number; and (vi) compression for the parameter feedback edge set number.

Original language	English (US)
Title of host publication	18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Editors	Neeldhara Misra, Magnus Wahlstrom
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959773058
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2023.31
State	Published - Dec 2023
Event	18th International Symposium on Parameterized and Exact Computation, IPEC 2023 - Amsterdam, Netherlands Duration: Sep 6 2023 → Sep 8 2023

Publication series

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

Conference

Conference	18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Country/Territory	Netherlands
City	Amsterdam
Period	9/6/23 → 9/8/23

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximation Algorithms
Dominating Set
Parameterized Complexity

Access to Document

10.4230/LIPIcs.IPEC.2023.31

Cite this

Koutis, I., Włodarczyk, M., & Zehavi, M. (2023). Sidestepping Barriers for Dominating Set in Parameterized Complexity. In N. Misra, & M. Wahlstrom (Eds.), 18th International Symposium on Parameterized and Exact Computation, IPEC 2023 Article 31 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 285). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.IPEC.2023.31

Koutis, Ioannis ; Włodarczyk, Michał ; Zehavi, Meirav. / Sidestepping Barriers for Dominating Set in Parameterized Complexity. 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. editor / Neeldhara Misra ; Magnus Wahlstrom. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{916413a3bb5e45819b50997905f6c7bb,

title = "Sidestepping Barriers for Dominating Set in Parameterized Complexity",

abstract = "We study the classic Dominating Set problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters treewidth, vertex modulator to constant treewidth and solution size; (iv,v) FPT-algorithms for the parameters vertex cover number and feedback edge set number; and (vi) compression for the parameter feedback edge set number.",

keywords = "Approximation Algorithms, Dominating Set, Parameterized Complexity",

author = "Ioannis Koutis and Micha{\l} W{\l}odarczyk and Meirav Zehavi",

note = "Publisher Copyright: {\textcopyright} 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 18th International Symposium on Parameterized and Exact Computation, IPEC 2023 ; Conference date: 06-09-2023 Through 08-09-2023",

year = "2023",

month = dec,

doi = "10.4230/LIPIcs.IPEC.2023.31",

language = "English (US)",

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

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Neeldhara Misra and Magnus Wahlstrom",

booktitle = "18th International Symposium on Parameterized and Exact Computation, IPEC 2023",

address = "Germany",

}

Koutis, I, Włodarczyk, M & Zehavi, M 2023, Sidestepping Barriers for Dominating Set in Parameterized Complexity. in N Misra & M Wahlstrom (eds), 18th International Symposium on Parameterized and Exact Computation, IPEC 2023., 31, Leibniz International Proceedings in Informatics, LIPIcs, vol. 285, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, Amsterdam, Netherlands, 9/6/23. https://doi.org/10.4230/LIPIcs.IPEC.2023.31

Sidestepping Barriers for Dominating Set in Parameterized Complexity. / Koutis, Ioannis; Włodarczyk, Michał; Zehavi, Meirav.
18th International Symposium on Parameterized and Exact Computation, IPEC 2023. ed. / Neeldhara Misra; Magnus Wahlstrom. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 31 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 285).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Sidestepping Barriers for Dominating Set in Parameterized Complexity

AU - Koutis, Ioannis

AU - Włodarczyk, Michał

AU - Zehavi, Meirav

PY - 2023/12

Y1 - 2023/12

N2 - We study the classic Dominating Set problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters treewidth, vertex modulator to constant treewidth and solution size; (iv,v) FPT-algorithms for the parameters vertex cover number and feedback edge set number; and (vi) compression for the parameter feedback edge set number.

AB - We study the classic Dominating Set problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters treewidth, vertex modulator to constant treewidth and solution size; (iv,v) FPT-algorithms for the parameters vertex cover number and feedback edge set number; and (vi) compression for the parameter feedback edge set number.

KW - Approximation Algorithms

KW - Dominating Set

KW - Parameterized Complexity

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

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

U2 - 10.4230/LIPIcs.IPEC.2023.31

DO - 10.4230/LIPIcs.IPEC.2023.31

M3 - Conference contribution

AN - SCOPUS:85180546134

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 18th International Symposium on Parameterized and Exact Computation, IPEC 2023

A2 - Misra, Neeldhara

A2 - Wahlstrom, Magnus

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 18th International Symposium on Parameterized and Exact Computation, IPEC 2023

Y2 - 6 September 2023 through 8 September 2023

ER -

Koutis I, Włodarczyk M, Zehavi M. Sidestepping Barriers for Dominating Set in Parameterized Complexity. In Misra N, Wahlstrom M, editors, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 31. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.IPEC.2023.31

Sidestepping Barriers for Dominating Set in Parameterized Complexity

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this