Skip to Main content Skip to Navigation
Journal articles

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

Julien Baste 1 Ignasi Sau Valls 1 Dimitrios M. Thilikos 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 2 O(tw) · n O(1) , called single-exponential, when H is either P 3 , P 4 , C 4 , the paw, the chair, and the banner for both {H}-M-Deletion and {H}-TM-Deletion, and when H = K 1,i , with i ≥ 1, for {H}-TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Ignasi Sau <>
Submitted on : Thursday, November 5, 2020 - 12:50:28 PM
Last modification on : Friday, January 8, 2021 - 11:22:06 AM
Long-term archiving on: : Saturday, February 6, 2021 - 7:14:58 PM


Files produced by the author(s)




Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms. Theoretical Computer Science, Elsevier, 2020, 814, pp.135-152. ⟨10.1016/j.tcs.2020.01.026⟩. ⟨lirmm-02989928⟩



Record views


Files downloads