We give a novel spectral approximation algorithm for the balanced (edge-)separator problem that, given a graph G, a constant balance b ∈ (0, 1/2], and a parameter γ, either finds an outputs a certificate that all b-balanced cuts in G have conductance at least γ, and runs in timeÕ(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute exp(−L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to exp(−A)v for a class of symmetric positive semidefinite (PSD) matrices A and a given vector v, in time roughlỹ O(m A), independent of the norm of A, where mA is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting symmetric and diagonally-dominant matrices inÕ(m A) time. Finally, using old and new uniform approximations to e −x we show how to obtain, via the Lanczos method, a simple algorithm to compute exp(−A)v for symmetric PSD matrices that runs in time roughly O(t A · A ), where tA is the time required for the computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O( √ γ), for balanced separator that runs in timeÕ( m / √ γ). This latter algorithm matches the running time, but improves on the approximation guarantee of the Evolving-Sets-based algorithm by Andersen and Peres for balanced separator.
Orecchia et al. use a variant of heat kernel random walks in their randomized algorithm for computing a cut in a graph with prescribed balance constraints REF .
Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
STOC '12
Computer Science Mathematics