Subexponential Parameterized Algorithms for Hitting Subgraphs

Fahad Panolan ( University of Leeds )

For a finite set F of graphs, the F-Hitting problem aims to compute, for a given n-vertex graph G (taken from some graph class) and a parameter k, a subset S of vertices in G of size at most k such 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)} poly(n), while it cannot be solved in 2^{o(k)}poly(n) time on general graphs assuming the ETH, follows from the seminal work of Lewis and Yannakakis. In this talk, we discuss subexponential parameterized algorithms for the F-Hitting problem on a broad family of graph classes that includes planar graphs, bounded-genus graphs, minor-free graphs and many important classes of geometric intersection graphs like map graphs, pseudo-disks, etc.

This is a joint work with Daniel Lokshtanov, Saket Saurabh, Jie Xue, and Meirav Zehavi.