Sidestepping Barriers for Dominating Set in Parameterized Complexity

Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publication18th International Symposium on Parameterized and Exact Computation, IPEC 2023
EditorsNeeldhara Misra, Magnus Wahlstrom
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773058
DOIs
StatePublished - Dec 2023
Event18th International Symposium on Parameterized and Exact Computation, IPEC 2023 - Amsterdam, Netherlands
Duration: Sep 6 2023Sep 8 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume285
ISSN (Print)1868-8969

Conference

Conference18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Country/TerritoryNetherlands
CityAmsterdam
Period9/6/239/8/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation Algorithms
  • Dominating Set
  • Parameterized Complexity

Fingerprint

Dive into the research topics of 'Sidestepping Barriers for Dominating Set in Parameterized Complexity'. Together they form a unique fingerprint.

Cite this