View article

In this paper, we consider the following graph partitioning problem: The input is an undirected graph G = (V, E), a balance parameter b ∊ (0, 1/2] and a target conductance value γ ∊ (0, 1). The output is a cut which, if non-empty, is of conductance at most O(f), for some function f(G, γ), and which is either balanced or well correlated with all cuts of conductance at most γ. In a seminal paper, Spielman and Teng [16] gave an -time algorithm for and used it to decompose graphs into a collection of near-expanders [18].

We present a new spectral algorithm for this problem which runs in time for f = √γ. Our result yields the first nearly-linear time algorithm for the classic Balanced Separator problem that achieves the asymptotically optimal approximation guarantee for spectral methods.

Our method has the advantage of being conceptually simple and relies on a primal-dual semidefinite-programming (SDP) approach. We first …