License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.4
URN: urn:nbn:de:0030-drops-85556
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8555/
Go to the corresponding LIPIcs Volume Portal


Baste, Julien ; Sau, Ignasi ; Thilikos, Dimitrios M.

Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth

pdf-format:
LIPIcs-IPEC-2017-4.pdf (0.7 MB)


Abstract

For a fixed collection of graphs F, the F-M-DELETION 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 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. 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 single-exponential algorithms use, in particular, the rank-based 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:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8555},
  URN =		{urn:nbn:de:0030-drops-85556},
  doi =		{10.4230/LIPIcs.IPEC.2017.4},
  annote =	{Keywords:  parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}

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: 23.02.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI