On approximate preprocessing for domination and hitting subgraphs with connected deletion sets

In this paper, we study the ConnectedH-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the ConnectedH-hitting set problem, we obtain an α-approximate kernel for every α>1 and complemen...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2019-11, Vol.105, p.158-170
Main Authors: Eiben, Eduard, Hermelin, Danny, Ramanujan, M.S.
Format: Article
Language:English
Subjects:
Kernelization
Parameterized complexity
Vertex deletion problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we study the ConnectedH-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the ConnectedH-hitting set problem, we obtain an α-approximate kernel for every α>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs, and provide an interpolation of approximate kernels between the known 3d-approximate kernel of constant size and 1-approximate kernel of size kO(d2).
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2019.05.001