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 st cuts over all pairs of
vertices s and t. It is wellknown that the value of a minimum st cut in a
graph equals the value of the maximum flow from s to t and the standard
algorithm for computing a minimum st 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 graphtheoretic arguments. We will
explain how to replace the PageRank computation by a multisource, multisink
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.
