Fast computation of small cuts via cycle space sampling

DOI10.1145/2000807.2000814MaRDI QIDQ3189030zbMATH OpenOpenAlexFDO

Authors

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsgraph connectivitylinear algebraparallel algorithmsrandomized algorithmsuniversal optimality

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph. In the model of distributed computing in a graph G=(V, E) with O(log V)-bit messages, our approach yields faster algorithms for several problems. The diameter of G is denoted by Diam, and the maximum degree by Delta. We obtain simple O(Diam)-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal --- i.e. a Omega(Diam)-time lower bound holds on every graph. We obtain a O(Diam+Delta/log V)-time distributed algorithm for finding cut vertices; this is faster than the best previous algorithm when Delta, Diam = O(sqrt(V)). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity. In the model of parallel computing on the EREW PRAM our approach yields a simple algorithm with optimal time complexity O(log V) for finding cut pairs and 3-edge-connected components.

Recommendations

• Fast Distributed Computation of Cuts Via Random Circulations
• Minimum cuts in near-linear time
• scientific article; zbMATH DE number 1256719
• A new approach to the minimum cut problem
• Almost-Tight Distributed Minimum Cut Algorithms

Cited in

(14)

• Fast distributed approximation for TAP and 2-edge-connectivity
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Fast distributed approximation for TAP and 2-edge-connectivity
• Fast Distributed Computation of Cuts Via Random Circulations
• A contraction algorithm for finding small cycle cutsets
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Optimal short cycle decomposition in almost linear time
• Tree-based coarsening and partitioning of complex networks
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Finding a small vertex cut on distributed networks
• Near-optimal distributed computation of small vertex cuts
• On packing low-diameter spanning trees
• Deterministic fault-tolerant connectivity labeling scheme
• Fault-tolerant labeling and compact routing schemes

This page was built for publication: Fast computation of small cuts via cycle space sampling

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