Approximating the Expansion Profile and Almost Optimal Local Graph Clustering

  • Shayan Oveis Gharan | Stanford

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.)

Speaker Details

Shayan Oveis Gharan is a graduate student at Stanford. His papers on approximating the TSP received best paper awards in SODA 2010 and FOCS 2011. See http://www.stanford.edu/~shayan/about_me.html for more information.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks