Subexponential Parameterized Algorithms for Hitting Subgraphs

For a finite set F of graphs, the F-Hitting problem aims to compute, for a given graph G (taken from some graph class G) of n vertices (and m edges) and a parameter k ∈ N, a set S of vertices in G such that |S| ≤ k and G -S does not contain any subgraph isomorphic to a graph in F. As a generic problem, F-Hitting subsumes many fundamental vertex-deletion problems that are well-studied in the literature. The F-Hitting problem admits a simple branching algorithm with running time 2 O(k) • n O(1) , while it cannot be solved in 2 o(k) • n O(1) time on general graphs assuming the ETH, follows from the seminal work of Lewis and Yannakakis. In this paper, we establish a general framework to design subexponential parameterized algorithms for the F-Hitting problem on a broad family of graph classes. Specifically, our framework yields algorithms that solve F-Hitting with running time 2 O(k c ) • n + O(m) for a constant c < 1 on any graph class G that admits balanced separators whose size is (strongly) sublinear in the number of vertices and polynomial in the size of a maximum clique. Examples include all graph classes of polynomial expansion (e.g., planar graphs, bounded-genus graphs, minor-free graphs, etc.) and many important classes of geometric intersection graphs (e.g., map graphs, intersection graphs of any fat geometric objects, pseudo-disks, etc.). Our algorithms also apply to the weighted version of F-Hitting, where each vertex of G has a weight and the goal is to compute the set S with a minimum weight that satisfies the desired conditions. The core of our framework, which is our main technical contribution, is an intricate subexponential branching algorithm that reduces an instance of F-Hitting (on the aforementioned graph classes) to 2 O(k c ) general hitting-set instances, where the Gaifman graph of each instance has treewidth O(k c ), for some constant c < 1 depending on F and the graph class.