BARC Talk by Dani Dorfman: Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

Abstract  

A well known sparsity notion of a cut (S, V\S) in a graph G=(V, E) is the expansion \phi(S, V\S) = |E(S, V\S)|/min(|S|, |V\S|). A Graph is said to be a \phi expander if all of its cuts have expansion at least \phi. Expanders appear in many cutting edge results, from subpolynomial dynamic connectivity to Laplacian solvers and even the recent almost linear time max flow algorithm.
All of these results use a graph partitioning algorithm called expander decomposition.

 A (\phi,\epsilon)-expander-decomposition of a graph G (with n vertices and m edges) is a partition of V into clusters V_1,...,V_k with conductance Phi(G[V_i]) > \phi, such that there are at most $\epsilon m$ inter-cluster edges. We give a randomized \tilde{O}(m) time algorithm for computing a (\phi, \phi log^2 n)-expander decomposition. This improves upon the (\phi, \phi log^3 n)-expander decomposition also obtained in \tilde{O}(m) time by [Saranurak and Wang, SODA 2019] (SW) and brings the number of inter-cluster edges within logarithmic factor of optimal.

One crucial component of SW's algorithm is a sparse cut algorithm called the Cut Matching Game of [Khandekar, Rao, Vazirani, JACM 2009] (KRV): This game is played between a cut player and a matching player through several rounds. The game might stop spontaneously and return a sparse cut or come to completion and certify that the graph is an expander. KRV devised a cut player that transform to an O(log^2 n) approximation algorithm of the sparsest cut problem.

SW used a non-stop version of the cut-matching game that comes to completion and finds an object called a near expander which is then used for the expander decomposition algorithm. The crux of our improvement is the design of a non-stop version of the cleverer cut player of [Orecchia, Schulman, Vazirani, Vishnoi, STOC 2008] (OSVV). The cut player of OSSV uses a more sophisticated random walk, a subtle potential function, and spectral arguments. Designing and analysing a non-stop version of this game was an explicit open question asked by SW.

Joint work with Daniel Agassy and Haim Kaplan, ICALP 2023.