Hypergraph k-cut for fixed k in deterministic polynomial time
This event is free and open to the publicAdd to Google Calendar
(Click “Event Website” above to access the zoom link.)
In the hypergraph k-cut problem, the input is a hypergraph along with a fixed constant k and the goal is to find a smallest subset of hyperedges whose removal ensures that the remaining hypergraph has at least k connected components. The graph k-cut problem is solvable in polynomial time (Goldschmidt and Hochbaum, 1994) while the complexity of the hypergraph k-cut problem was open. In this talk, I will present the first deterministic polynomial-time algorithm to solve the hypergraph k-cut problem. Our algorithm relies on novel structural results that provide new insights even for the graph k-cut problem.
Based on joint work with Chandra Chekuri.