In the "expansion profile" problem and the "small-set expander" problem we are interested in the following question: given a graph and a parameter k, find the subset of k or fewer vertices with the smallest expansion. Using the "evolving sets" algorithm of Andersen and Peres, we provide the following approximation guarantee: if there is a set of size at most k and expansion h, we can find a set of size at most k^(1+1/c) and expansion at most O( (ch)^(1/2) ), for any c0. Furthermore, the running time of the algorithm is almost linear in the size of the output set. This is the first algorithm for the expansion profile problem that does not lose factors of (log n)^(Omega(1)) in the expansion. Our result also resolve the open problem to design a "local graph clustering" algorithm with an approximation guarantee close to the guarantee of the Cheeger inequalities and with a running time nearly linear in the size of the output. (Talk based on joint work with Luca Trevisan.)
3