Finding Small Sparse Cuts Locally by Random Walk
Tsz Chiu Kwok, Lap Chi Lau · arXiv (Cornell University) · 2012
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 1/k. - If there is a subset U with conductance ϕand vol(U) 2ln(k)/k. These algorithms can be implemented locally using truncated random walk, with running time almost linear to the output size. This provides a local graph partitioning algorithm with a better conductance guarantee when k is sublinear.