Theory Seminar
An Algorithm for Hypergraph k-Cut
Karthik ChandrasekaranAssistant ProfessorUniversity of Illinois, Urbana-Champaign
WHERE:
3725 Beyster Building
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.