Graph Connectivity Using Star Contraction

Explore a 31-minute lecture by Sagnik Mukhopadhyay from the University of Birmingham on graph connectivity using star contraction. Delve into the complexity of determining edge connectivity in simple graphs with cut queries. Discover a bounded-error randomized algorithm that computes edge connectivity with O(n) cut queries and a quantum algorithm achieving O(√n) cut queries. Learn about the novel star contraction technique for randomly contracting edges while preserving non-trivial minimum cuts. Compare this method to the 2-out contraction technique and understand its efficient implementation via cut queries. Examine the implications of these findings for connectivity problems, symmetric submodular function minimization, and quantum-classical separations in graph algorithms. Gain insights into the joint work with Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, and Danupon Nanongkai, as presented at FOCS 2022.

Graph Connectivity Using Star Contraction