Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos · SIAM Journal on Computing · 2023
Abstract. For a fixed finite collection of graphs [Formula: see text] the [Formula: see text]-M-Deletion problem is as follows: given an [Formula: see text]-vertex input graph [Formula: see text] find the minimum number of vertices that intersect all minor models in [Formula: see text] of the graphs in [Formula: see text]. by Courcelle’s Theorem, this problem can be solved in time [Formula: see text] where [Formula: see text] is the treewidth of [Formula: see text] for some function [Formula: see text] depending on [Formula: see text]. In a recent series of articles, we have initiated the program of optimizing asymptotically the function [Formula: see text]. Here we provide an algorithm showing that [Formula: see text] for every collection [Formula: see text]. Prior to this work, the best known function [Formula: see text] was double-exponential in [Formula: see text]. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [ Proc. of the 25 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802–1811] for the particular case [Formula: see text] and of Kociumaka and Pilipczuk [ Algorithmica, 81 (2019), pp. 3655–3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [ Inform. Comput., 256 (2017), pp. 62–82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections [Formula: see text] [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135–152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56–77], our algorithm yields the following complexity dichotomy when [Formula: see text] contains a single connected graph [Formula: see text] assuming the Exponential Time Hypothesis: [Formula: see text] if [Formula: see text] is a contraction of the chair or the banner , and [Formula: see text] otherwise.