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 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},