Hols, EvaMaria C. ;
Kratsch, Stefan
On Kernelization for Edge Dominating Set under Structural Parameters
Abstract
In the NPhard Edge Dominating Set problem (EDS) we are given a graph G=(V,E) and an integer k, and need to determine whether there is a set F subseteq E of at most k edges that are incident with all (other) edges of G. It is known that this problem is fixedparameter tractable and admits a polynomial kernelization when parameterized by k. A caveat for this parameter is that it needs to be large, i.e., at least equal to half the size of a maximum matching of G, for instances not to be trivially negative. Motivated by this, we study the existence of polynomial kernelizations for EDS when parameterized by structural parameters that may be much smaller than k.
Unfortunately, at first glance this looks rather hopeless: Even when parameterized by the deletion distance to a disjoint union of paths P_3 of length two there is no polynomial kernelization (under standard assumptions), ruling out polynomial kernelizations for many smaller parameters like the feedback vertex set size. In contrast, somewhat surprisingly, there is a polynomial kernelization for deletion distance to a disjoint union of paths P_5 of length four. As our main result, we fully classify for all finite sets H of graphs, whether a kernel size polynomial in X is possible when given X such that each connected component of GX is isomorphic to a graph in H.
BibTeX  Entry
@InProceedings{hols_et_al:LIPIcs:2019:10275,
author = {EvaMaria C. Hols and Stefan Kratsch},
title = {{On Kernelization for Edge Dominating Set under Structural Parameters}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {36:136:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10275},
doi = {10.4230/LIPIcs.STACS.2019.36},
annote = {Keywords: Edge dominating set, kernelization, structural parameters}
}
12.03.2019
Keywords: 

Edge dominating set, kernelization, structural parameters 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

12.03.2019 