Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

Aditya Anand, Thatchaphol Saranurak, Yunfan Wang

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 a…