MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Fomin, Fedor V.
Lokshtanov, Daniel
Misra, Neeldhara
Philip, Geevarghese
Saurabh, Saket		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Fomin, Fedor V.
Lokshtanov, Daniel
Misra, Neeldhara
Saurabh, Saket
Editor(s):
Schwentick, Thomas
D{\"u}rr, Christoph		dblp
dblp
Not MPII Editor(s):
Schwentick, Thomas
D{\"u}rr, Christoph
BibTeX cite key*:
FominLokshtanovMisraPhilipSaurabh2011
Title, Booktitle
Title*:
Hitting forbidden minors: Approximation and Kernelization
forbidden_minors_stacs.pdf (3041.21 KB)
Booktitle*:
28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany
Event, URLs
Conference URL::
http://www.stacs2011.de/
Downloading URL:
http://drops.dagstuhl.de/opus/volltexte/2011/3010/pdf/20.pdf
Event Address*:
Dortmund, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 March 2011
Event End Date:
12 March 2011
Publisher
Name*:
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
URL:
http://www.dagstuhl.de/
Address*:
Dagstuhl, Germany
Type:
Vol, No, Year, pp.
Series:
Leibniz International Proceedings in Informatics
Volume:
9
Number:
Month:
Pages:
189-200
Year*:
2011
VG Wort Pages:
ISBN/ISSN:
978-3-939897-25-5
Sequence Number:
DOI:
10.4230/LIPIcs.STACS.2011.189
Note, Abstract, ©
(LaTeX) Abstract:
We study a general class of problems called $p$-\textsc{$\mathcal{F}$-Deletion}
problems. In an $p$-\textsc{$\mathcal{F}$-Deletion} 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 ${\cal F}$ of forbidden minors. We obtain a number of algorithmic results
on the $p$-\textsc{$\mathcal{F}$-Deletion} problem when $\mathcal{F}$ contains a planar graph. We give
\begin{itemize}

\item a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leves, as an induced subgraph, where $t$ is a fixed integer.

\item 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.
\end{itemize}
Finally, we obtain polynomial kernels for the case when $\cal 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 well-studied problems such as {\sc Vertex Cover}, {\sc Feedback Vertex Set} and \textsc{Diamond Hitting Set}
.
The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on
topological graph classes.
URL for the Abstract:
http://drops.dagstuhl.de/opus/volltexte/2011/3010/
Keywords:
Kernelization, Forbidden minors, Approximation
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{FominLokshtanovMisraPhilipSaurabh2011,
AUTHOR = {Fomin, Fedor V. and Lokshtanov, Daniel and Misra, Neeldhara and Philip, Geevarghese and Saurabh, Saket},
 EDITOR = {Schwentick, Thomas and D{\"u}rr, Christoph},
 TITLE = {Hitting forbidden minors: Approximation and Kernelization},
 BOOKTITLE = {28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany},
 PUBLISHER = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
 YEAR = {2011},
 VOLUME = {9},
 PAGES = {189--200},
 SERIES = {Leibniz International Proceedings in Informatics},
 ADDRESS = {Dortmund, Germany},
 ISBN = {978-3-939897-25-5},
 DOI = {10.4230/LIPIcs.STACS.2011.189},
}

Entry last modified by Geevarghese Philip, 07/08/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
04/22/2012 13:09:28
Revision
1.
0.


Editor
Geevarghese Philip
Geevarghese Philip


Edit Date
12/08/2012 04:41:42 AM
04/22/2012 01:09:28 PM


File Attachment Icon
forbidden_minors_stacs.pdf