MPI-INF D1 Publications: Proceedings Article: Hitting forbidden minors: Approximation and Kernelization

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

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


(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)

	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