Theory Seminar: Hypergraph K-Cut in Randomized Polynomial Time

Hypergraph K-Cut in Randomized Polynomial Time

Abstract: 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.

Bio: Karthekeyan Chandrasekaran is an assistant professor in Industrial and Enterprise Systems Engineering and an affiliate assistant professor in Computer Science at UIUC. He received his Ph.D. in Algorithms, Combinatorics and Optimization from Georgia Tech. Prior to joining UIUC, he was a Simons Postdoctoral Fellow in the Theory of Computation group at Harvard University. His research interests are in combinatorial optimization, design and analysis of algorithms, and integer programming.