Abstract:

Edge-modification problems ask for the minimal number of edge additions/deletions needed to make a graph satisfy some property. A (meta) problem of this type, which was raised by Yannakakis in 1981, asks to determine for which properties P, it is NP-hard to compute the smallest number of edge deletions needed to make a graph satisfy P. Despite being extensively studied in the past 40 years, this problem is still wide open, even when P is the property of being H-free, for some fixed graph H. Let Rem_H(G) denote the smallest number of edge deletions needed to turn G into an H-free graph. Alon, Shapira and Sudakov [Annals of Math. 2009] proved that if H is not bipartite, then computing Rem_H(G) is NP-hard. They left open the problem of classifying the bipartite graphs H for which computing Rem_H(G) is NP-hard. We resolve this problem when H is a forest, showing that computing Rem_H(G) is polynomial-time solvable if H is a star forest and NP-hard otherwise. Our main innovation lies in introducing a new graph theoretic approach, which differs significantly from all prior works on this subject. In particular, we prove new results concerning a famous conjecture of Erdős and Sós regarding the Turán number of trees.
Joint work with Lior Gishboliner and Asaf Shapira.