# A Simple Framework for Finding Balanced Sparse Cuts via APSP

Preprint · Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva

- Archive id: arxiv:2209.08845
- Published: 2022-09-19
- arXiv: https://arxiv.org/abs/2209.08845
- Source URL: https://arxiv.org/abs/2209.08845
- PDF: https://arxiv.org/pdf/2209.08845
- Provenance: arxiv

## Abstract

We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solving unit-weight multi-commodity flows with standard ball growing arguments. Using Dijkstra's algorithm for computing the shortest paths afresh every time gives a very simple algorithm that runs in time $\\widetilde{O}(m^2/φ)$ and finds an $\\widetilde{O}(φ)$-sparse balanced cut, when the given graph has a $φ$-sparse balanced cut. Combining our algorithm with known deterministic data-structures for answering approximate All Pairs Shortest Paths (APSP) queries under increasing edge weights (decremental setting), we obtain a simple deterministic algorithm that finds $m^{o(1)}φ$-sparse balanced cuts in $m^{1+o(1)}/φ$ time. Our deterministic almost-linear time algorithm matches the state-of-the-art in randomized and deterministic settings up to subpolynomial factors, while being significantly simpler to understand and analyze, especially compared to the only almost-linear time deterministic algorithm, a recent breakthrough by Chuzhoy-Gao-Li-Nanongkai-Peng-Saranurak (FOCS 2020).

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.