Mikkel Thorup: Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Tuesday, March 17, 2015 - 4:15pm to 5:15pm
Refreshments:
Light Refreshments
Location:
D 463 (Star) ***change of location***
Speaker:
Mikkel Thorup, University of Copenhagen, Denmark
Seminar group:
Abstract
We present a deterministic near-linear time algorithm that computes the edge-connectivity and
finds a minimum cut for a simple undirectedunweighted graph G with n vertices and m edges.
This is the first o(mn) time deterministic algorithm for the problem. In near-linear
time we can also construct the classic cactus representation of all minimum cuts.
The previous fastest deterministic algorithm by Gabow from STOC'91took ~O(m+k^2 n),
where k is the edge connectivity, but k could be Omega(n).
At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum
cut problem. As he points out, there is nobetter way of certifying the minimality of the returned
cut than to use Gabow's slower deterministic algorithm and compare sizes.
Our main technical contribution is a near-linear time algorithm that contract vertex sets of a simple
input graph G with minimum degree d, producing a multigraph with ~O(m/d) edges which
preserves all minimum cuts of G with at least 2 vertices on each side.
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.
Joint work with Ken-ichi Kawarabayashi, National Institute of Informatics, Tokyo, Japan