Compact cactus representations of all non-trivial min-cuts

DOI10.1016/J.DAM.2020.03.046MaRDI QIDQ1983141zbMATH OpenOpenAlexWikidataFDO

Authors On-Hei S. Lo, Jens M. Schmidt, Mikkel Thorup

Publication date 15 September 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.03865

zbMATH Keywords

cactus representationcontraction-based sparsificationDAG representationmin-cuts enumerationnon-trivial min-cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Connectivity (05C40)

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 $ildeO(n/delta)$ vertices and $ildeO(n)$ edges that preserves all non-trivial min-cuts of $G$, where $delta$ is the minimum degree of $G$ and $ildeO$ 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 $ildeO(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 $ildeO(m)+O(n^2/delta)$ time for every simple graph, which improves the previous best time bound $O(nm)$ given by Gusfield and Naor.

Recommendations

• A near-linear time algorithm for constructing a cactus representation of minimum cuts
• A fast algorithm for cactus representations of minimum cuts
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Deterministic global minimum cut of a simple graph in near-linear time
• scientific article; zbMATH DE number 1187160

Cites work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A matroid approach to finding edge connectivity and packing arborescences
• A near-linear time algorithm for constructing a cactus representation of minimum cuts
• Canonical cactus representation for miminum cuts
• Deterministic Edge Connectivity in Near-Linear Time
• Extracting maximal information about sets of minimum cuts
• Local flow partitioning for faster edge connectivity
• Multi-Terminal Network Flows

Cited in

(6)

• Improved approximations for relative survivable network design
• scientific article; zbMATH DE number 1263227 (Why is no real title available?)
• Generalized cut trees for edge-connectivity
• Canonical cactus representation for miminum cuts
• Compact representations of cuts
• Fast and deterministic approximations for \(k\)-cut

This page was built for publication: Compact cactus representations of all non-trivial min-cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1983141)