Skip to Main content Skip to Navigation
Journal articles

Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds

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 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 f F such that F-M-Deletion can be solved in time f F (tw) · n O(1) on n-vertex graphs. We prove that f F (tw) = 2 2 O(tw·log tw) for every collection F , that f F (tw) = 2 O(tw·log tw) if F contains a planar graph, and that f F (tw) = 2 O(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.
Document type :
Journal articles
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02989921
Contributor : Ignasi Sau <>
Submitted on : Thursday, November 5, 2020 - 12:48:10 PM
Last modification on : Friday, November 20, 2020 - 11:56:02 AM
Long-term archiving on: : Saturday, February 6, 2021 - 7:14:37 PM

File

SIDMA-M128714.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2020, 34 (3), pp.1623-1648. ⟨10.1137/19M1287146⟩. ⟨lirmm-02989921⟩

Share

Metrics

Record views

35

Files downloads

63