2026-07-26T00:38:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19450 2024-03-06T11:04:05Z ddc:004 open_access

Sidestepping Barriers for Dominating Set in Parameterized Complexity Koutis, Ioannis Włodarczyk, Michał Zehavi, Meirav Dominating Set Parameterized Complexity Approximation Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ioannis Koutis and Michał Włodarczyk and Meirav Zehavi 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.31 urn:nbn:de:0030-drops-194506 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.31 eng https://creativecommons.org/licenses/by/4.0/legalcode