Deterministic Global Minimum Cut in Near-Linear Time
Date and Time
Tuesday, October 14, 2014 - 4:30pm to 5:30pm
Location
Computer Science 402
Type
Talk
Speaker
Host
Robert Tarjan
We present a deterministic Õ(m) time algorithm finding a global minimum cut of an undirected unweigthed graph G with n nodes and m edges. In particular, this identifies the edge connectivity k of G.
The previous fastest deterministic algorithm by Gabow from STOC'91 took Õ(km) time. At STOC'96 Karger presented randomized near-linear time Monte Carlo algorithm for the problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm.
In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.
The previous fastest deterministic algorithm by Gabow from STOC'91 took Õ(km) time. At STOC'96 Karger presented randomized near-linear time Monte Carlo algorithm for the problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm.
In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.
