Paper detail

Tight Running Time Lower Bounds for Vertex Deletion Problems

For a graph class $Π$, the $Π$-Vertex Deletion problem has as input an undirected graph $G=(V,E)$ and an integer $k$ and asks whether there is a set of at most $k$ vertices that can be deleted from $G$ such that the resulting graph is a member of $Π$. By a classic result of Lewis and Yannakakis [J. Comput. Syst. Sci. '80], $Π$-Vertex Deletion is NP-hard for all hereditary properties $Π$. We adapt the original NP-hardness construction to show that under the Exponential Time Hypothesis (ETH) tight complexity results can be obtained. We show that $Π$-Vertex Deletion does not admit a $2^{o(n)}$-time algorithm where $n$ is the number of vertices in $G$. We also obtain a dichotomy for running time bounds that include the number $m$ of edges in the input graph: On the one hand, if $Π$ contains all independent sets, then there is no $2^{o(n+m)}$-time algorithm for $Π$-Vertex Deletion. On the other hand, if there is a fixed independent set that is not contained in $Π$ and containment in $Π$ can determined in $2^{O(n)}$ time or $2^{o(m)}$ time, then $Π$-Vertex Deletion can be solved in $2^{O(\sqrt{m})}+O(n)$ or $2^{o({m})}+O(n)$ time, respectively. We also consider restrictions on the domain of the input graph $G$. For example, we obtain that $Π$-Vertex Deletion cannot be solved in $2^{o(\sqrt{n})}$ time if $G$ is planar and $Π$ is hereditary and contains and excludes infinitely many planar graphs. Finally, we provide similar results for the problem variant where the deleted vertex set has to induce a connected graph.