Fomin, Fedor V. ;
Lokshtanov, Daniel ;
Misra, Neeldhara ;
Philip, Geevarghese ;
Saurabh, Saket
Hitting forbidden minors: Approximation and Kernelization
Abstract
We study a general class of problems called FDeletion problems. In an FDeletion problem, we are asked whether a subset of at most k
vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the FDeletion problem when F contains a planar graph. We give
 a linear vertex kernel on graphs excluding tclaw K_(1,t), the star with t leaves, as an induced subgraph, where t is a fixed integer.
 an approximation algorithm achieving an approximation ratio of O(log^(3/2) OPT), where $OPT$ is the size of an optimal solution on general undirected graphs.
Finally, we obtain polynomial kernels for the case when F only contains graph theta_c as a minor for a fixed integer c. The graph theta_c consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses wellstudied problems such as Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2011:3010,
author = {Fedor V. Fomin and Daniel Lokshtanov and Neeldhara Misra and Geevarghese Philip and Saket Saurabh},
title = {{Hitting forbidden minors: Approximation and Kernelization}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {189200},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3010},
URN = {urn:nbn:de:0030drops30103},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.189},
annote = {Keywords: kernelization}
}
2011
Keywords: 

kernelization 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Issue date: 

2011 
Date of publication: 

2011 