Balanced graph partitioning

Abstract

In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υ • n<over>k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2.