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 Library locked




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

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 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


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
forbidden_minors_stacs.pdf