Deterministic Edge Connectivity in Near-Linear Time
From MaRDI portal
Abstract: We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts. The previous fastest deterministic algorithm by Gabow from STOC'91 took ~O(m+k^2 n), where k is the edge connectivity, but k could be Omega(n). At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm and compare sizes. Our main technical contribution is a near-linear time algorithm that contract vertex sets of a simple input graph G with minimum degree d, producing a multigraph with ~O(m/d) edges which preserves all minimum cuts of G with at least 2 vertices on each side. In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.
Recommendations
- scientific article; zbMATH DE number 437577
- Faster deterministic fully-dynamic graph connectivity
- Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
- Distributed edge connectivity in sublinear time
- Engineering nearly linear-time algorithms for small vertex connectivity
- A Fast Algorithm for Optimally Increasing the Edge Connectivity
- Efficient algorithms for computing all low s-t edge connectivities and related problems
- Dynamic graph connectivity in polylogarithmic worst case time
- Fast edge-searching and related problems
- Efficient algorithm for computing all low s-t edge connectivities in directed graphs
Cited in
(31)- An improved linear edge bound for graph linkages
- Compact cactus representations of all non-trivial min-cuts
- Faster connectivity in low-rank hypergraphs via expander decomposition
- Finding densest \(k\)-connected subgraphs
- Optimal offline dynamic 2, 3-edge/vertex connectivity
- Deterministic global minimum cut of a simple graph in near-linear time
- scientific article; zbMATH DE number 437577 (Why is no real title available?)
- A Fast Algorithm for Optimally Increasing the Edge Connectivity
- Local flow partitioning for faster edge connectivity
- Local flow partitioning for faster edge connectivity
- Distributed edge connectivity in sublinear time
- Minimum Cuts in Surface Graphs
- scientific article; zbMATH DE number 7740902 (Why is no real title available?)
- Expanders via local edge flips in quasilinear time
- Generalized cut trees for edge-connectivity
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Minimum cut in \(O(m \log^2 n)\) time
- Minimum cut in O(m^2 n time
- Bisection width, discrepancy, and eigenvalues of hypergraphs
- Deterministic minimum cut in poly-logarithmic maximum flows
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Worst-case to expander-case reductions: derandomized and generalized
- Deterministic minimum Steiner cut in maximum flow time
- Practical expander decomposition
- Tree-packing revisited: faster fully dynamic min-cut and arboricity
- Higher connectivity in directed graphs (invited talk)
- Faster dynamic 2-edge connectivity in directed graphs
- Efficient contractions of dynamic graphs -- with applications
- Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut
- Cut-query algorithms with few rounds
- Minimum+1 Steiner cut and dual edge sensitivity oracle: bridging gap between global and (s,t)-cut
This page was built for publication: Deterministic Edge Connectivity in Near-Linear Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625670)
