TY - JOUR

T1 - Polynomial kernels for hitting forbidden minors under structural parameterizations

AU - Jansen, Bart M.P.

AU - Pieterse, Astrid

PY - 2020/11/12

Y1 - 2020/11/12

N2 - We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-DELETION 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 kO(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 F-DELETION problem by the size of a vertex modulator whose removal results in a graph of constant treedepth η. We prove that for each set F of connected graphs and constant η, the F-DELETION problem parameterized by the size of a treedepth-η modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-DELETION. 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 G−X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F-DELETION solution from a single connected component of G−X. 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 F-DELETION such as VERTEX COVER and FEEDBACK VERTEX SET. It also generalizes earlier preprocessing results for F-DELETION parameterized by a vertex cover, which is a treedepth-one modulator.

AB - We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-DELETION 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 kO(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 F-DELETION problem by the size of a vertex modulator whose removal results in a graph of constant treedepth η. We prove that for each set F of connected graphs and constant η, the F-DELETION problem parameterized by the size of a treedepth-η modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-DELETION. 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 G−X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F-DELETION solution from a single connected component of G−X. 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 F-DELETION such as VERTEX COVER and FEEDBACK VERTEX SET. It also generalizes earlier preprocessing results for F-DELETION parameterized by a vertex cover, which is a treedepth-one modulator.

KW - F-minor free deletion

KW - Kernelization

KW - Structural parameterization

KW - Treedepth modulator

UR - http://www.scopus.com/inward/record.url?scp=85088933201&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.07.009

DO - 10.1016/j.tcs.2020.07.009

M3 - Article

AN - SCOPUS:85088933201

SN - 0304-3975

VL - 841

SP - 124

EP - 166

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -