Fast approximate graph partitioning algorithms

We study graph partitioning problems on graphs with edge capacities and ver tex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity rho-separators. A rho-se parator is a subset of edges whose removal partitions the vertex set into c onnected components such that the sum of the vertex weights in each compone nt is at most rho times the weight of the graph. We present a new and simpl e O(log n)-approximation algorithm for minimum capacity rho-separators whic h is based on spreading metrics yielding an O(log n)-approximation algorith m both for b-balanced cuts and k-balanced partitions. In particular, this r esult improves the previous best known approximation factor for k-balanced partitions in undirected graphs by a factor of O(log k). We enhance these r esults by presenting a version of the algorithm that obtains an O(log OPT)- approximation factor. The algorithm is based on a technique called spreadin g metrics that enables us to formulate directly the minimum capacity rho-se parator problem as an integer program. We also introduce a generalization c alled the simultaneous separator problem, where the goal is to find a minim um capacity subset of edges that separates a given collection of subsets si multaneously. We extend our results to directed graphs for values of rho gr eater than or equal to 1/2. We conclude with an efficient algorithm for com puting an optimal spreading metric for rho-separators. This yields more eff icient algorithms for computing b-balanced cuts than were previously known.