Approximating Small Sparse Cuts

Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak

Abstract

Finding the "weakest link" in a network—the set of edges or vertices whose removal most efficiently disconnects the graph—is a cornerstone of computer science. Known as the Sparsest Cut problem, it underpins applications from community detection to VLSI design. Traditionally, approximation ratios for these problems scale with the total number of vertices $n$. This paper presents a paradigm shift, introducing the first polynomial-time $O(\text{polylog } k)$-approximation algorithms for Sparsest Cut and Small Set Expansion, where $k$ is the size of the optimal cut. By leveraging "sample set" techniques and introducing a local version of the cut-matching game, the authors achieve performance bounds independent of the total graph size when the cut is small.

Introduction

The paper addresses two fundamental graph partitioning problems: Sparsest Cut, which seeks a cut with a minimum ratio of edges cut to vertices separated, and Small Set Expansion (SSE), which focuses on finding sparse cuts for sets of a specific maximum size $s$.

While the $O(\sqrt{\log n})$ approximation by Arora, Rao, and Vazirani (ARV) remains the gold standard for Sparsest Cut, its error scales with the total graph size. In massive real-world graphs where the optimal cut $k$ is much smaller than $n$, this error becomes disproportionately large. The authors propose a parametric approximation approach, aiming for error ratios that are functions of $k$ alone. This bridges the gap between traditional approximation algorithms and Fixed Parameter Tractability (FPT).

Methodology

The researchers utilize three primary algorithmic pillars to achieve these results:

  1. Sample Sets for Sparse Cuts: The authors extend a technique originally designed for balanced cuts. They prove that for any sparse cut, there exists a small "sample set" of terminal vertices (roughly $O(k \cdot \text{polylog } k)$) that preserves the cut's sparsity within a small error margin.
  2. LP Rounding with Terminals: They adapt Linear Programming (LP) frameworks to operate on these terminal sets. By solving an LP on the entire graph but weighting the objective function based on the sample set, they can extract approximations dependent on $k$.
  3. Local Cut-Matching Game: The "cut-matching game" is a classic framework for finding expanders. The authors develop a local variant that ensures every set of size $s$ expands in $O(\log s)$ rounds. This innovation allows for finding sparse cuts in almost-linear time ($m^{1+o(1)}$).

Key Results

The paper establishes several new upper and lower bounds for graph partitioning problems. A significant finding is the sharp contrast between edge and vertex cuts. While edge-based SSE admits an $O(\log k)$ approximation, the authors demonstrate that Small Set Vertex Expansion is significantly harder, showing no $2^{o(k)}$ approximation exists under the Strongish Planted Clique Hypothesis (SPCH).

Summary of approximation ratios and computational complexity for various cut problems.

Beyond the core results shown in the table above, the authors improve the bound on the size of multicut mimicking networks from $k^{O(\log^3 k)}$ to $k^{O(\log^2 k)}$, which has direct implications for kernelization in parameterized complexity.

Discussion and Future Work

This work represents a significant step toward "data-aware" graph partitioning. However, several open questions remain:

  • SSE Efficiency: While Sparsest Cut can now be solved in almost-linear time, achieving similar efficiency for Small Set Expansion remains an open challenge.
  • Vertex Cut Refinement: The $O(\log \log n\phi)$ term in the Vertex Sparsest Cut result indicates a lingering (though small) dependence on $n$. Determining if this is a fundamental barrier of the sample set approach is a key area for future research.
  • Polylog Optimization: Future work may explore whether the $O(\log^2 k)$ bound for fast Sparsest Cut can be tightened to $O(\log k)$.

By ensuring that algorithm accuracy and speed improve when the solution is simple (small $k$), this research provides a more robust framework for analyzing large-scale networks.

Summary updated

BibTeX
@inproceedings{anand2024approximating,
  author = {Aditya Anand and Euiwoong Lee and Jason Li and Thatchaphol Saranurak},
  title = {{Approximating Small Sparse Cuts}},
  booktitle = {STOC},
  year = {2024},
  doi = {10.1145/3618260.3649747},
}
Figure