Compact Cactus Representations of all Non-Trivial Min-Cuts.

Content Provider	Semantic Scholar
Author	Lo, On-Hei Solomon Schmidt, Jens M. Thorup, Mikkel
Copyright Year	2018
Abstract	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 $\tilde{O}(n/\delta)$ vertices and $\tilde{O}(n)$ edges that preserves all non-trivial min-cuts of $G$, where $\delta$ is the minimum degree of $G$ and $\tilde{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/\delta)$ vertices and $O(n)$ edges, preserves all non-trivial min-cuts and can be computed in near-linear time $\tilde{O}(m)$, where $m$ is the number of edges of $G$. We also obtain that every simple graph has $O((n/\delta)^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/\delta)$ 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 $\tilde{O}(m) + O(n^2 / \delta)$ time for every simple graph, which improves the previous best time bound $O(nm)$ given by Gusfield and Naor.
File Format	PDF HTM / HTML
DOI	10.1016/j.dam.2020.03.046
Alternate Webpage(s)	https://arxiv.org/pdf/1810.03865v2.pdf
Alternate Webpage(s)	https://static-curis.ku.dk/portal/files/239808854/OA_Compact_Cactus_Representations_of_all_Non_Trivial_Min_Cuts.pdf
Alternate Webpage(s)	http://www4.tu-ilmenau.de/combinatorial-optimization/Lo2020a.pdf
Alternate Webpage(s)	http://export.arxiv.org/pdf/1810.03865
Alternate Webpage(s)	https://doi.org/10.1016/j.dam.2020.03.046
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article