Hitting minors on bounded treewidth graphs. I. General upper bounds

Julien Baste, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

For a finite collection of graphs F, the F-M-Deletion problem consists in, given a graph G and an integer k, deciding 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 are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-Deletion can be solved in time fF(tw) · nO(1) on n-vertex graphs. We prove that fF(tw) = 22O(tw·log tw) for every collection F, that fF(tw) = 2O(tw·log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic.

Original languageEnglish (US)
Pages (from-to)1623-1648
Number of pages26
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number3
DOIs
StatePublished - 2020

Keywords

  • Dynamic programming
  • Exponential time hypothesis
  • Graph minors
  • Hitting minors
  • Parameterized complexity
  • Topological minors
  • Treewidth

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

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

Cite this