Cut Query Algorithms with Star Contraction

We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge connectivity with $O(n)$ cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with $\tilde{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 “center” 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 randomized 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 randomized query lower bound for minimizing a symmetric submodular function. The quantum algorithm from item (ii) gives a nearlyquadratic separation with the randomized 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 $\tilde{O}(\sqrt{}$n) matrix-vector multiplication queries to its adjacency matrix. Finally, we demonstrate the use of star contraction outside of the cut query setting by designing a one-pass semi-streaming algorithm for computing edge connectivity in the complete vertex arrival setting. This contrasts with the edge arrival setting where two passes are required.

Authors

• Simon Apers
• Yuval Efron
• Pawel Gawrychowski
• Troy Lee
• Sagnik Mukhopadhyay
• Danupon Nanongkai

Keywords

• Computer science
• Analytical models
• Quantum algorithm
• Upper bound
• Symmetric matrices
• Computational modeling
• Stars
• Star Contraction
• Cut Queries
• Matrix Multiplication
• Weak Connections
• Complex Communication
• Simple Graph
• Complex Connections
• Edge Connectivity
• Quantum Algorithms
• Incident Edges
• Minimum Cut
• High Probability
• Lower Bound
• Undirected
• Model Algorithm
• Information Bits
• Extra Term
• Minimum Degree
• Use Of The Fact
• Neighboring Vertices
• Constant Probability
• Adjacency Matrix Of Graph
• Max-Cut
• Sparse Connectivity
• Single Query
• Outgoing Edges
• Stream Model
• Constant Degree
• Deterministic Case
• F. 1. 1 Models of Computation
• F. 1. 3 Complexity Measures and Classes
• F. 2 Analysis of Algorithms and Problem Complexity