Let $mathcal{C}$ and $mathcal{D}$ be hereditary graph classes. Consider the following problem: given a graph $Ginmathcal{D}$, find a largest, in terms of the number of vertices, induced subgraph of $G$ that belongs to $mathcal{C}$. We prove that it can be solved in $2^{o(n)}$ time, where $n$ is the number of vertices of $G$, if the following conditions are satisfied: * the graphs in $mathcal{C}$ are sparse, i.e., they have linearly many edges in terms of the number of vertices; * the graphs in $mathcal{D}$ admit balanced separators of size governed by their density, e.g., $mathcal{O}(Delta)$ or $mathcal{O}(sqrt{m})$, where $Delta$ and $m$ denote the maximum degree and the number of edges, respectively; and * the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes $mathcal{C}$ and $mathcal{D}$: * a largest induced forest in a $P_t$-free graph can be found in $2^{tilde{mathcal{O}}(n^{2/3})}$ time, for every fixed $t$; and * a largest induced planar graph in a string graph can be found in $2^{tilde{mathcal{O}}(n^{3/4})}$ time.
Download