Balanced graph partitioning

We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter nu >= 1, no component contains more than. nu . n/k of the graph vertices. For k = 2 and nu = 1 this problem is equivalent to the well-known Minimum Bisection problem for which an approximation algorithm with a polylogarithmic approximation guarantee has been presented in [FK]. For arbitrary k and nu >= 2 a bicriteria approximation ratio of O(log n) was obtained by Even et al. [ENRS1] using the spreading metrics technique. We present a bicriteria approximation algorithm that for any constant nu> 1 runs in polynomial time and guarantees an approximation ratio of O(log(1.5) n) ( for a precise statement of the main result see Theorem 6). For nu = 1 and k >= 3 we show that no polynomial time approximation algorithm can guarantee a finite approximation ratio unless P = NP.