Compact cactus representations of all non-trivial min-cuts

DOI10.1016/J.DAM.2020.03.046zbMATH Open1472.05085arXiv1810.03865OpenAlexW3015233796WikidataQ109517115 ScholiaQ109517115MaRDI QIDQ1983141FDOQ1983141

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)

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.

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

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

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)

Cites Work

• A matroid approach to finding edge connectivity and packing arborescences
• Multi-Terminal Network Flows
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Extracting maximal information about sets of minimum cuts
• 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
• Local flow partitioning for faster edge connectivity

Cited In (6)

• Improved approximations for relative survivable network design
• Title not available (Why is that?)
• Generalized cut trees for edge-connectivity
• Title not available (Why is that?)
• Canonical cactus representation for miminum cuts
• Compact representations of cuts

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)