Prof. Monika Henzinger presents Finding the global minimum cut:Flows beat PageRank

Prague Computer Science Seminar:

In this talk we will survey the history and the state of the art of algorithms
for finding minimum cuts in graphs, including some new developments. We will
focus on global minimum cuts, which is the minimum of s-t cuts over all pairs of
vertices s and t. It is well-known that the value of a minimum s-t cut in a
graph equals the value of the maximum flow from s to t and the standard
algorithm for computing a minimum s-t cut still uses a maximum flow computation.
Using that approach, however, leads to a quite inefficient algorithm for
computing the global minimum cut, requiring n flow computations, where n is the
number of vertices of the graph.

Indeed until recently the fastest algorithm for global minimum cut in unweighted
graphs was not based on flow computation but was using multiple PageRank
computations in combination with various graph-theoretic arguments. We will
explain how to replace the PageRank computation by a multi-source, multi-sink
flow computation that results in the fastest known algorithm for global minimum
cut in unweighted graphs. This is a joint work with Satish Rao and Di Wang.