2026-07-23T15:20:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8555 2024-03-06T10:41:29Z ddc:004 open_access

Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth Baste, Julien Sau, Ignasi Thilikos, Dimitrios M. parameterized complexity graph minors treewidth hitting minors topological minors dynamic programming Exponential Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Baste and Ignasi Sau and Dimitrios M. Thilikos 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.4 urn:nbn:de:0030-drops-85556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode