Hitting minors on bounded treewidth graphs. III. Lower bounds

Julien Baste, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

For a finite fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S⊆V(G) with |S|≤k such that G∖S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function fF such that F-M-DELETION can be solved in time fF(tw)⋅nO(1) on n-vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, fF(tw)=2Ω(tw), even if G is planar. Our main result is that if F contains a single connected graph H that is either P5 or is not a minor of the banner, then fF(tw)=2Ω(tw⋅log⁡tw).

Original languageEnglish (US)
Pages (from-to)56-77
Number of pages22
JournalJournal of Computer and System Sciences
Volume109
DOIs
StatePublished - May 2020

Keywords

  • Dynamic programming
  • Exponential Time Hypothesis
  • Graph minors
  • Hitting minors
  • Parameterized complexity
  • Topological minors
  • Treewidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Hitting minors on bounded treewidth graphs. III. Lower bounds'. Together they form a unique fingerprint.

Cite this