  For a graph class $\Pi$, the $\Pi$-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 $\Pi$. By a classic result of Lewis and Yannakakis [J.
Comput. Syst. Sci. '80], $\Pi$-Vertex Deletion is NP-hard for all hereditary
properties $\Pi$. 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 $\Pi$-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 $\Pi$ contains all independent sets, then
there is no $2^{o(n+m)}$-time algorithm for $\Pi$-Vertex Deletion. On the other
hand, if there is a fixed independent set that is not contained in $\Pi$ and
containment in $\Pi$ can determined in $2^{O(n)}$ time or $2^{o(m)}$ time, then
$\Pi$-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 $\Pi$-Vertex
Deletion cannot be solved in $2^{o(\sqrt{n})}$ time if $G$ is planar and $\Pi$
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.
