Finding Small Sparse Cuts Locally by Random Walk

Tsz Chiu Kwok, Lap Chi Lau

We study the problem of finding a small sparse cut in an undirected graph. Given an undirected graph G=(V,E) and a parameter k <= |E|, the small sparsest cut problem is to find a s…