TY - GEN
T1 - Sidestepping Barriers for Dominating Set in Parameterized Complexity
AU - Koutis, Ioannis
AU - Włodarczyk, Michał
AU - Zehavi, Meirav
N1 - Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
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 -