Abstract
I will primarily talk about the complexity of determining the edge connectivity of a simple graph with cut queries. I will show that (i) there is a bounded-error randomised algorithm that computes edge connectivity with O(n) cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with O(\sqrt n) cut queries. To prove these results we introduce a new technique, called star contraction, to randomly contract edges of a graph while preserving non-trivial minimum cuts. In star contraction, vertices randomly contract an edge incident on a small set of randomly chosen ‘centre’ vertices. In contrast to the related 2-out contraction technique of Ghaffari, Nowicki, and Thorup [SODA'20], star contraction only contracts vertex-disjoint star subgraphs, which allows it to be efficiently implemented via cut queries.
The O(n) bound from item (i) was not known even for the simpler problem of connectivity, and it improves the O(n \log^3 n) upper bound by Rubinstein, Schramm, and Weinberg [ITCS'18]. The bound is tight under the reasonable conjecture that the randomised communication complexity of connectivity is \Omega(n \log n), an open question since the seminal work of Babai, Frankl, and Simon [FOCS'86]. The bound also excludes using edge connectivity on simple graphs to prove a superlinear randomised query lower bound for minimising a symmetric submodular function. The quantum algorithm from item (ii) gives a nearly-quadratic separation with the randomised complexity, and addresses an open question of Lee, Santha, and Zhang [SODA'21]. The algorithm can alternatively be viewed as computing the edge connectivity of a simple graph with O(\sqrt n) matrix-vector multiplication queries to its adjacency matrix.
The result is a joint work with Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, and Danupon Nanongkai and appeared in FOCS 2022.