Skip to main content

2019 | OriginalPaper | Buchkapitel

A Turing Kernelization Dichotomy for Structural Parameterizations of \(\mathcal {F}\)-Minor-Free Deletion

verfasst von : Huib Donkers, Bart M. P. Jansen

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

For a fixed finite family of graphs \(\mathcal {F}\), the \(\mathcal {F}\)-Minor-Free Deletion problem takes as input a graph G and an integer \(\ell \) and asks whether there exists a set \(X \subseteq V(G)\) of size at most \(\ell \) such that \(G-X\) is \(\mathcal {F}\)-minor-free. For \(\mathcal {F} =\{K_2\}\) and \(\mathcal {F} =\{K_3\}\) this encodes Vertex Cover and Feedback Vertex Set respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. Such a polynomial kernelization also exists for any \(\mathcal {F}\) containing a planar graph but no forests.
In this paper we show that \(\mathcal {F}\)-Minor-Free Deletion parameterized by the feedback vertex number is \(\mathsf {MK[2]}\)-hard for \(\mathcal {F} = \{P_3\}\). This rules out the existence of a polynomial kernel assuming \(\mathsf {NP}\not \subseteq \mathsf {coNP/poly}\), and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any \(\mathcal {F}\) not containing a \(P_3\)-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth \(\min {{\,\mathrm{tw}\,}} (\mathcal {F})\), where \(\min {{\,\mathrm{tw}\,}} (\mathcal {F})\) denotes the minimum treewidth of the graphs in \(\mathcal {F}\). For the other case, where \(\mathcal {F}\) contains a \(P_3\)-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to \(\mathcal {F}\)-Subgraph-Free Deletion.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
If \(\mathcal {F} \) contains no forests, the size of an optimal solution is at most the size of a feedback vertex set: the kernel for the solution-size parameterization can be used.
 
Literatur
2.
Zurück zum Zitat Berge, C.: Sur le couplage maximum d’un graphe. Comptes rendus hebdomadaires des séances de l’Académie des sciences 247, 258–259 (1958)MathSciNetMATH Berge, C.: Sur le couplage maximum d’un graphe. Comptes rendus hebdomadaires des séances de l’Académie des sciences 247, 258–259 (1958)MathSciNetMATH
5.
Zurück zum Zitat Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566–597 (2010)MathSciNetCrossRef Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566–597 (2010)MathSciNetCrossRef
Metadaten
Titel
A Turing Kernelization Dichotomy for Structural Parameterizations of -Minor-Free Deletion
verfasst von
Huib Donkers
Bart M. P. Jansen
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-30786-8_9