Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms

Julien Baste, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


For a finite collection of graphs F, the F-M-DELETION (resp. F-TM-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 (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G, denoted by tw, and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2O(tw)⋅nO(1), called single-exponential, when H is either P3, P4, C4, the paw, the chair, and the banner for both {H}-M-DELETION and {H}-TM-DELETION, and when H=K1,i, with i≥1, for {H}-TM-DELETION. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of {H}-M-DELETION in terms of H.

Original languageEnglish (US)
Pages (from-to)135-152
Number of pages18
JournalTheoretical Computer Science
StatePublished - Apr 24 2020


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms'. Together they form a unique fingerprint.

Cite this