Jansen, Bart M. P. ;
Pieterse, Astrid
Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
Abstract
We investigate polynomialtime preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of graphs F, the FDeletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance (G,k) can be reduced in polynomial time to an equivalent one of size k^{O(1)}. In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the FDeletion problem by the size of a vertex modulator whose removal results in a graph of constant treedepth eta.
We prove that for each set F of connected graphs and constant eta, the FDeletion problem parameterized by the size of a treedeptheta modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or wellquasiordering, which are sources of algorithmic nonconstructivity in earlier works on FDeletion. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of GX. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal FDeletion solution from a single connected component of GX. By bounding the number of different types of behavior that can occur by a polynomial in X, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of FDeletion such as Vertex Cover and Feedback Vertex Set. It also generalizes earlier preprocessing results for FDeletion parameterized by a vertex cover, which is a treedepthone modulator.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2018:9511,
author = {Bart M. P. Jansen and Astrid Pieterse},
title = {{Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {48:148:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9511},
URN = {urn:nbn:de:0030drops95119},
doi = {10.4230/LIPIcs.ESA.2018.48},
annote = {Keywords: Kernelization, Fminor free deletion, Treedepth modulator, Structural parameterization}
}
14.08.2018
Keywords: 

Kernelization, Fminor free deletion, Treedepth modulator, Structural parameterization 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

14.08.2018 