Sidestepping Barriers for Dominating Set in Parameterized Complexity

Autor:	Koutis, Ioannis, Włodarczyk, Michał, Zehavi, Meirav
Rok vydání:	2023
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	We study the classic {\sc 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 {\em treewidth}, {\em vertex modulator to constant treewidth} and {\em solution size}; (iv,v) FPT-algorithms for the parameters {\em vertex cover number} and {\em feedback edge set number}; and (vi) compression for the parameter {\em feedback edge set number}. Comment: Accepted to IPEC'23
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2309.15645 Zobrazit plný text záznamu View this record from Arxiv