Graphs and Matroids - Lior Gishboliner

Tuesday, March 18, 2025 3:00 pm - 4:00 pm EDT (GMT -04:00)

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.