Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2019) |
last year
(2018) |
two years ago
(2017) |
Notes URL
Action:
login to update
Options:
Library locked
Goto entry point
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
Attachment(s)
:
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
URL of the conference:
http://www.stacs2011.de/
URL for downloading the paper:
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
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 01:09:28 PM
Revision
1.
0.
Editor
Geevarghese Philip
Geevarghese Philip
Edit Date
12/08/2012 04:41:42 AM
04/22/2012 01:09:28 PM
Attachment Section
Attachment Section
View attachments here:
forbidden_minors_stacs.pdf
forbidden_minors_stacs.pdf