A sparsest cut of a weighted graph minimizes the ratio of the capacity crossing
a cut to the demand separated by that cut.
For a finite undirected
graph with vertex set 
, nonnegative capacities 
, and nonnegative
demands 
on unordered pairs of distinct vertices, with at
least one positive demand, the objective is
 |
over nonempty proper subsets 
with positive separated demand (Rothvoss 2016, p. 1).
A mincut minimizes crossing capacity
alone, whereas the demand normalization here also depends on 
.
When every demand is 1, the problem is uniform
sparsest cut.
