Cheeger-type approximation for sparsest $st$-cut

Robert Krauthgamer, Tal Wagner

We introduce the $st$-cut version the Sparsest-Cut problem, where the goal is to find a cut of minimum sparsity among those separating two distinguished vertices $s,t\in V$. Clearl…