Approximating Small Balanced Vertex Separators in Almost Linear Time

Summary

For a graph G with n vertices and m edges, we give a randomized Las Vegas algorithm that approximates a small balanced vertex separator of G in almost linear time. More precisely, we show the following, for any 2 3 ≤ α < 1 and any 0 < ε < 1 − α: If G contains an α-separator of size K, then our algorithm finds an (α + ε)-separator of size O(ε −1K2 log1+o(1) n) in time O(ε −1K3m log2+o(1) n) w.h.p. In particular, if K ∈ O(polylog n), then we obtain an (α + ε)-separator of size O(ε −1 polylog n) in time O(ε −1m polylog n) w.h.p. The presented algorithm does not require knowledge of K.