For a k-uniform hypergraph H, the H-freeness edge modification problem is the algorithmic problem of finding, for a given k-uniform input G, the distance of G from H-freeness, i.e., the minimum number of edges that need to be deleted from G in order to obtain an H-free hypergraph. I will present new results on this general problem. In particular, I will show that if H is not k-partite, then it is NP-hard to compute the distance to H-freeness, and even to approximate this distance up to an additive error of n^{k-delta} for any fixed delta > 0. This resolves a special case of a problem raised by Ailon and Alon.

This is joint work with Yevgeny Levanzov and Asaf Shapira.