All-Pairs Minimum Cut using O(n^7/4) Cut Queries

2025/10/19 by Yotam Kenneth-Mordoch, Robert Krauthgamer, Kenneth-Mordoch, Yotam +1 · 1 citation
Business, Management and Accounting · Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management

paper · pdf · doi:10.48550/arxiv.2510.16741

openalex publication_date 2025/10/19 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28

Abstract

We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph G=(V,E) with n vertices, our randomized algorithm constructs a Gomory-Hu tree of G, and thus solves the all-pairs minimum cut problem, using O(n^7/4) cut queries.

Citations

• Deterministic Almost-Linear-Time Gomory-Hu Trees
• Cut-Query Algorithms with Few Rounds
• Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
• On the cut-query complexity of approximating max-cut
• Improved Lower Bounds for Submodular Function Minimization
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• Cut query algorithms with star contraction
• Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
• Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
• APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
• A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
• Deterministic Weighted Expander Decomposition in Almost-linear Time
• A Note on Isolating Cut Lemma for Submodular Function Minimization
• Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
• On the cut dimension of a graph
• Cut-Equivalent Trees are Optimal for Min-Cut Queries
• Graph Connectivity and Single Element Recovery via Linear and OR Queries
• Minimizing Convex Functions with Rational Minimizers
• New Query Lower Bounds for Submodular Function MInimization
• A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• Polynomial Pass Lower Bounds for Graph Streaming Algorithms
• A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Cited by

• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow

Related

• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
• Computing exact minimum cuts without knowing the graph
• Cut-Query Algorithms with Few Rounds
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs