A Turing kernelization dichotomy for structural parameterizations of ℱ -minor-free deletion

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

Abstract

For a fixed finite family of graphs FF, the FF-Minor-Free Deletion problemtakes as input a graph G and an integer ℓℓ and asks whether there exists a set X⊆V(G)X⊆V(G) of size at most ℓℓ such that G−XG−X is FF-minor-free. For F={K2}F={K2} and F={K3}F={K3} this encodes VertexCover and FeedbackVertex Set respectively. When parameterized by thefeedback vertex number of G these two problems areknown to admit a polynomial kernelization. Such a polynomial kernelization alsoexists for any FF containing a planar graph but no forests.

In this paper we show that FF-Minor-Free Deletion parameterizedby the feedback vertex number is MK[2]MK[2]-hard for F={P3}F={P3}. This rules out the existence of a polynomial kernel ssuming NP⊈coNP/polyNP⊈coNP/poly, and also gives evidence that the problem does not admit a polynomialTuring kernel. Our hardness result generalizes to any FF not containing a P3P3-subgraph-free graph, using as parameter the vertex-deletion distance totreewidth mintw(F)mintw(F), where mintw(F)mintw(F) denotes the minimum treewidth of the graphs in FF. For the other case, where FF contains a P3P3-subgraph-free graph, we present a polynomial Turing kernelization. Ourresults extend to FF-Subgraph-Free Deletion.

 

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers
EditorsIgnasi Sau, Dimitrios M. Thilikos
Place of PublicationCham
PublisherSpringer
Pages106-119
Number of pages14
ISBN (Electronic)978-3-030-30786-8
ISBN (Print)978-3-030-30785-1
DOIs
Publication statusPublished - 2019
Event45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Spain
Duration: 19 Jun 201921 Jun 2019

Publication series

NameLecture Notes in Computer Science
Volume11789

Conference

Conference45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019
CountrySpain
CityCatalonia
Period19/06/1921/06/19

Keywords

  • Minor-free deletion
  • Structural parameterization
  • Subgraph-free deletion
  • Turing kernelization

Fingerprint Dive into the research topics of 'A Turing kernelization dichotomy for structural parameterizations of ℱ -minor-free deletion'. Together they form a unique fingerprint.

Cite this