Compact cactus representations of all non-trivial min-cuts

Recently, Kawarabayashi and Thorup presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existence of vertex subsets of a simple graph G on n vertices whose contractions leave a multigraph with O ̃ ( n / δ ) vertices and O ̃ ( n ) edges that preserves all non-trivial min-cuts of G , where δ is the minimum degree of G and O ̃ hides logarithmic factors. We present a simple argument that improves this contraction-based sparsifier by eliminating the poly-logarithmic factors, that is, we show a contraction-based sparsification that leaves O ( n / δ ) vertices and O ( n ) edges, preserves all non-trivial min-cuts and can be computed in near-linear time O ̃ ( m ) , where m is the number of edges of G . We also obtain that every simple graph has O ( ( n / δ ) 2 ) non-trivial min-cuts. Our approach allows to represent all non-trivial min-cuts of a graph by a cactus representation, whose cactus graph has O ( n / δ ) vertices. Moreover, this cactus representation can be derived directly from the standard cactus representation of all min-cuts in linear time. We apply this compact structure to show that all min-cuts can be explicitly listed in O ̃ ( m ) + O ( n 2 / δ ) time for every simple graph, which improves the previous best time bound O ( n m ) given by Gusfield and Naor.