# Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

arXiv: https://arxiv.org/abs/2410.18704 · HTML: https://mlsanity.com/paper/2410.18704/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2024.

## Built on by (most cited first, 1 of 1)

- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)

## Abstract (arXiv)

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(n5/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(n5/3) queries. We also show efficient cut-query implementations of versions of expander decomposition and isolating cuts, which may be of independent interest.