An Algorithm for Hypergraph k-Cut

In the hypergraph k-cut problem, the input is a hypergraph along with a 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 is open. In this talk, I will present a randomized polynomial-time algorithm to solve the hypergraph k-cut problem. Along the way, I will also present a random contraction algorithm to compute hypergraph min-cut, thus generalizing the well-known random contraction algorithm for graph min-cut due to Karger.