Minimum Cuts in Near-Linear Time

1998/12/08 by David R. Karger, Karger, David R. · 13 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #G.3 #Manufacturing Process and Optimization #Optimization and Packing Problems #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/9812007

arxiv created 1998/12/08 · openalex publication_date 1998/12/08 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a ``semi-duality'' between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log³ n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n² log n) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O(n² log³ n). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.

Cited by

• Pseudodeterministic Algorithms for Minimum Cut Problems
• Approximating Directed Connectivity in Almost-Linear Time
• Using random spanning trees in survivable networks design
• Greedy matroid base packings with applications to dynamic graph density and orientations
• Set System Approximation for Binary Integer Programs: Reformulations and Applications
• Hedgegraph Polymatroids
• Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
• Thin Trees via k-Respecting Cut Identities
• FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks
• From small eigenvalues to large cuts, and Chowla's cosine problem
• Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
• Simple Algorithms for Fully Dynamic Edge Connectivity
• Deterministic Almost-Linear-Time Gomory-Hu Trees

Related

• A Simple Algorithm for Minimum Cuts in Near-Linear Time
• Minimum Cut in O(mlog² n) Time
• Finding the KT partition of a weighted graph in near-linear time
• A Note on a Recent Algorithm for Minimum Cut
• LP Relaxation and Tree Packing for Minimum k-cuts