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, the objective
is
 |
over nonempty proper subsets 
with positive separated demand
(Rothvoss 2016). 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.
