ARC Colloquium: Anupam Gupta (CMU)

Algorithms & Randomness Center (ARC)

Anupam Gupta (CMU)

Monday, October 18, 2021

Klaus 1116 East - 11:00 am


Title:  Finding and Counting k-cuts in Graphs

Abstract: For an undirected graph with edge weights, a k-cut is a set of edges whose deletion breaks the graph into at least k connected components. How fast can we find a minimum-weight k-cut? And how many minimum k-cuts can a graph have? The two problems are closely linked. In 1996 Karger and Stein showed how to find a minimum k-cut in approximately n^{2k-2} time; their proof also bounded the number of minimum k-cuts by n^{2k-2}, using the probabilistic method. Prior to our work, these were the best results known. Moreover, both these results were not known to be tight, except for the case of k=2 (which is the classical problem of finding graph min-cuts).

In this talk, we show how both these results can be improved to approximately n^k. We discuss how extremal bounds for set systems, plus a refined analysis of the Karger's contraction algorithm, can give near-optimal bounds.

This is joint work with Euiwoong Lee (U.Michigan), Jason Li (CMU), and David Harris (Maryland).


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Monday, October 18, 2021
    12:00 pm - 1:00 pm