#### Theory Seminar

# An Algorithm for Hypergraph k-Cut

Karthik ChandrasekaranAssistant ProfessorUniversity of Illinois, Urbana-Champaign

WHERE:

3725 Beyster BuildingMap

WHEN:

Friday, March 20, 2020 @ 10:30 am - 11:30 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

SHARE:

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.

Based on joint work with Chao Xu and Xilin Yu.