Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

2024/10/24 by Aditya Anand, Thatchaphol Saranurak, Anand, Aditya +3 · 4 citations
Computer Science · #Distributed systems and fault tolerance #Quantum Computing Algorithms and Architecture #Cellular Automata and Applications

paper · pdf · doi:10.48550/arxiv.2410.18704

Abstract

We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an n-vertex graph G, our algorithm makes \widetildeO(n^5/3) queries to compute the global min-cut in G. As a key ingredient, we also show an algorithm for finding s-t max-flows of size \widetildeO(n) in \widetildeO(n^5/3) queries. We also show efficient cut-query implementations of versions of expander decomposition and isolating cuts, which may be of independent interest.

Cited by

• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• A (Very) Nearly Optimal Sketch for k-Edge Connectivity Certificates
• Minimum s--t Cuts with Fewer Cut Queries
• All-Pairs Minimum Cut using O(n^7/4) Cut Queries

Related

• On the cut-query complexity of approximating max-cut
• Computing exact minimum cuts without knowing the graph
• Minimum s--t Cuts with Fewer Cut Queries
• Cut-Query Algorithms with Few Rounds
• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow