Approximation Algorithm for Sparsest k-Partitioning

Original · EN

Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as ϕG(S):= w(E(S,S)) w(S), w(S), where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k-partition P₁,, Pₖ of the vertex set so as to minimize ϕₖ(P₁,, Pₖ):= ᵢ ϕG(Pᵢ). Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 -)k-partition of the vertex set such that each piece has expansion at most Oε(√ n k) times OPT. We also study balanced versions of this problem.