Title:New results on the complexity of edge-modification problems
| Speaker: | Lior Gishboliner |
| Affiliation: | University of Toronto |
| Location: | MC 5479 |
Abstract:
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 the computational complexity of 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 a joint work with Yevgeny Levanzov and Asaf Shapira.