Deterministic Global Minimum Cut in Near-Linear Time – University of Copenhagen

Deterministic Global Minimum Cut in Near-Linear Time

EADS talk by Mikkel Thorup, Monday October 13th at 1-2 pm.

Abstract

Mikkel Thorup

We present a deterministic Õ(m) time algorithm for 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 a 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 Google by Brin and Page from 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.