Baste, Julien ;
Sau, Ignasi ;
Thilikos, Dimitrios M.
Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth
Abstract
For a fixed collection of graphs F, the FMDELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that GS does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of FMDELETION 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 FMDELETION can be solved in time f_F(tw)n^{O(1)} on nvertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds:
 f_{K_4}(w) = 2^{Theta(wlog w)}.
 f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4.
 f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5.
The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The singleexponential algorithms use, in particular, the rankbased approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.
BibTeX  Entry
@InProceedings{baste_et_al:LIPIcs:2018:8555,
author = {Julien Baste and Ignasi Sau and Dimitrios M. Thilikos},
title = {{Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {4:14:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8555},
URN = {urn:nbn:de:0030drops85556},
doi = {10.4230/LIPIcs.IPEC.2017.4},
annote = {Keywords: parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}
02.03.2018
Keywords: 

parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 