Subexponential-time algorithms for finding large induced sparse subgraphs

Let $\mathcal{C}$ and $\mathcal{D}$ be hereditary graph classes. Consider the following problem: given a graph $G\in \mathcal{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}(\mathrm{\Delta })$ or $\mathcal{O}(\sqrt{m})$, where $\mathrm{\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\mathrm{/}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\mathrm{/}4})}$ time.