A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut

Abstract

Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqrt{(\log n)/\epsilon })$-approximation using $O(n^{\epsilon }{\log }^{O(1)}n)$ maxflows for any $\epsilon \in [\Theta (1/\log n),\Theta (1)]$. It works by solving the SDP relaxation of [Arora-Rao-Vazirani, STOC 2004] using the Multiplicative Weights Update algorithm (MW) of [Arora-Kale, JACM 2016]. To implement one MW step, Sherman approximately solves a multicommodity flow problem using another application of MW. Nested MW steps are solved via a certain ``chaining'' algorithm that combines results of multiple calls to the maxflow algorithm. We present an alternative approach that avoids solving the multicommodity flow problem and instead computes ``violating paths''. This simplifies Sherman's algorithm by removing a need for a nested application of MW, and also allows parallelization: we show how to compute $O(\sqrt{(\log n)/\epsilon })$-approximation via $O({\log }^{O(1)}n)$ maxflows using $O(n^{\epsilon })$ processors. We also revisit Sherman's chaining algorithm, and present a simpler version together with a new analysis.

Accepted to Transactions on Algorithms (TALG). Preliminary version appeared in ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2024)