TY - GEN

T1 - A complexity dichotomy for hitting connected minors on bounded treewidth graphs

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

AU - Baste, Julien

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
Copyright © 2020 by SIAM

PY - 2020

Y1 - 2020

N2 - For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f(tw)·nO(1), where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f(tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw)·nO(1) for the more general problem where all minor models of connected graphs in a finite family F need to be hit. 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. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case F = {K5,K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

AB - For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f(tw)·nO(1), where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f(tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw)·nO(1) for the more general problem where all minor models of connected graphs in a finite family F need to be hit. 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. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case F = {K5,K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

UR - http://www.scopus.com/inward/record.url?scp=85077384435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85077384435&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85077384435

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 951

EP - 970

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

Y2 - 5 January 2020 through 8 January 2020

ER -