A near-linear time algorithm for constructing a cactus representation of minimum cuts

David R. Karger, Debmalya Panigrahi

Abstract

We present an Õ(m) (near-linear) time Monte Carlo algorithm for constructing the cactus data structure, a useful representation of all the global minimum edge cuts of an undirected graph. Our algorithm represents a fundamental improvement over the best previous (quadratic time) algorithms: because there can be quadratically many min-cuts, our algorithm must avoid looking at all min-cuts during the construction, but nonetheless builds a data structure representing them all. Our result closes the gap between the (near-linear) time required to find a single min-cut and that for (implicitly) finding all the min-cuts.
BibTeX
@inproceedings{karger2009near,
  author = {David R. Karger and Debmalya Panigrahi},
  title = {{A near-linear time algorithm for constructing a cactus representation of minimum cuts}},
  booktitle = {SODA},
  year = {2009},
  doi = {10.1137/1.9781611973068.28},
}
Figure