Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles SIAM Journal on Discrete Mathematics Year : 2020

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

Julien Baste
Ignasi Sau

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.
Fichier principal
Vignette du fichier
SIDMA-M128714.pdf (581.64 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02989921 , version 1 (05-11-2020)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More