We study vertex‑deletion problems on string graphs and, more generally, on $H$‑induced‑minor‑free graphs. For any fixed graph $H$, fixed non‑negative integer $t$, and fixed monadic second‑order formula $\phi$, we ask for a minimum set $S$ such that $G\! -\! S$ has treewidth at most $t$ and satisfies $\phi$. This framework captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to any fixed bounded‑treewidth graph.
We present an algorithm running in $2^{k^{2/3}\log^{O(1)}k}\,n^{O(1)}$ time on $H$‑induced‑minor‑free graphs, where $k$ is the optimum deletion‑set size. This positively resolves the open questions raised by Bonnet and Rz\k{a}.{z}ewski (Algorithmica 2019) and Berthe et al. (ICALP 2025) about the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Compared with previous parameterized algorithms that applied only to more restricted graph classes, our result achieves a substantial improvement on a much broader family.
When the property defined by $\phi$ is hereditary, we also obtain a quasi‑polynomial time approximation scheme (QPTAS), i.e., a $(1+\varepsilon)$‑approximate solution in quasi‑polynomial time. Both the subexponential algorithm and the QPTAS rely on the same new structural and algorithmic insights.
Review: This work breaks the time barrier for vertex‑deletion problems on wide graph classes, offering a powerful template for designing efficient parameterized and approximation algorithms on even more complex structures.