Computing exact minimum cuts without knowing the graph

2017/11/08 by Rubinstein, Aviad, Schramm, Tselil, Weinberg, S. Matthew · 5 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1711.03165

Abstract

We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S ⊂ V, the oracle returns the size of the cut between S and V ∖ S. We provide algorithms computing an exact minimum s-t cut in G with O(n^5/3) queries, and computing an exact global minimum cut of G with only O(n) queries (while learning the graph requires Θ(n²) queries).

Cited by

• Combinatorial Optimization using Comparison Oracles
• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• Cut Query Reachability for DAGs with Subquadratic Queries
• A (Very) Nearly Optimal Sketch for k-Edge Connectivity Certificates
• Minimum s--t Cuts with Fewer Cut Queries

Related

• Minimum s--t Cuts with Fewer Cut Queries
• On the cut-query complexity of approximating max-cut
• Cut-Query Algorithms with Few Rounds
• Query Complexity of Global Minimum Cut
• New Query Lower Bounds for Submodular Function MInimization