# Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?

arXiv: https://arxiv.org/abs/1303.2730 · HTML: https://mlsanity.com/paper/1303.2730/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2013.

## Built on by (most cited first, 1 of 1)

- [SpEx: A Spectral Approach to Explainable Clustering](https://mlsanity.com/paper/2511.00885/) (2025)

## Abstract (arXiv)

In the em nonuniform sparsest cut problem, given two undirected graphs G and H over the same set of vertices V, we want to find a cut (S,V-S) that minimizes the ratio between the fraction of G-edges that are cut and the fraction of H-edges that are cut. The ratio (which is at most 1 in an optimal solution) is called the em sparsity of the cut. In the em uniform sparsest cut problem, H is a clique over V. If G is regular, it is possible to find a solution to the uniform sparsest cut of cost O(√opt) in nearly linear time. Is such an approximation, which we call "Cheege-type" approximation, achievable in the non-uniform case? We show that the answer is negative, assuming the Unique Games Conjecture, for general H. Furthermore, the Leighton-Rao linear programming relaxation and the spectral relaxation fail to find such an approximation even if H is a clique over a subset of vertices. Using semidefinite programming, however, we can find Cheeger-type approximations in polynomial time whenever the adjacency matrix of H has rank 1. (This includes the cases in which H is a clique over a subset of vertices.)