Uniform kernelization complexity of hitting forbidden minors

A.C. Giannopoulou, B.M.P. Jansen, D. Lokshtanov, S. Saurabh

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
79 Downloads (Pure)

Abstract

The F-MINOR-FREE DELETION problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether κ vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. At FOCS 2012, Fomin et al. showed that the special case when F contains at least one planar graph has a kernel of size f (F) · κg(F) for some functions f and g. They left open whether this PLANAR F-MINOR-FREE DELETION problem has kernels whose size is uniformly polynomial, of the form f (F) · κc for some universal constant c. We prove that some PLANAR F-MINOR-FREE DELETION problems do not have uniformly polynomial kernels (unless NP ⊆ coNP/poly), not even when parameterized by the vertex cover number. On the positive side, we consider the problem of determining whether κ vertices can be removed to obtain a graph of treedepth at most η. We prove that this problem admits uniformly polynomial kernels with O(κ6) vertices for every fixed η.

Original languageEnglish
Article number35
Pages (from-to)1-35
JournalACM Transactions on Algorithms
Volume13
Issue number3
DOIs
Publication statusPublished - 1 Mar 2017

Keywords

  • Kernelization
  • Lower bounds
  • Minor-free deletion
  • Treedepth

Fingerprint Dive into the research topics of 'Uniform kernelization complexity of hitting forbidden minors'. Together they form a unique fingerprint.

Cite this