  Graph modification problems ask for the minimal number of vertex/edge
additions/deletions needed to make a graph satisfy some predetermined property.
A (meta) problem of this type, which was raised by Yannakakis in 1981, asks to
determine for which properties ${\mathcal P}$, it is NP-hard to compute the
smallest number of edge deletions needed to make a graph satisfy ${\mathcal
P}$. Despite being extensively studied in the past 40 years, this problem is
still wide open. In fact, it is open even when ${\mathcal P}$ is the property
of being $H$-free, for some fixed graph $H$. In this case we use
$\text{rem}_{H}(G)$ to denote the smallest number of edge deletions needed to
turn $G$ into an $H$-free graph.
  Alon, Sudakov and Shapira [Annals of Math. 2009] proved that if $H$ is not
bipartite, then computing $\text{rem}_{H}(G)$ is NP-hard. They left open the
problem of classifying the bipartite graphs $H$ for which computing
$\text{rem}_{H}(G)$ is NP-hard. In this paper we resolve this problem when $H$
is a forest, showing that computing $\text{rem}_{H}(G)$ is polynomial-time
solvable if $H$ is a star forest and NP-hard otherwise. Our main innovation in
this work lies in introducing a new graph theoretic approach for Yannakakis's
problem, which differs significantly from all prior works on this subject. In
particular, we prove new results concerning an old and famous conjecture of
Erd\H{o}s and S\'os, which are of independent interest.
