Balanced partitions of trees and applications

Abstract

We study the k-BALANCED PARTITIONING problem in which the vertices of a graph are to be partitioned into k sets of size at most dn=ke while minimising the cut-size, which is the number of edges connecting vertices in dierent sets. The problem is well studied for general graphs, for which it cannot be approximated within any nite factor in polynomial time. However, little is known about restricted graph classes. We show that for trees k-BALANCED PARTITIONING remains surprisingly hard. In particular, approximating the cut-size is APX-hard even if the maximum degree of the tree is constant. If instead the diameter of the tree is bounded by a constant, we show that it is NP-hard to approximate the cut-size within nc, for any constant c < 1. In the face of the hardness results, we show that allowing near-balanced solutions, in which there are at most (1+")dn=ke vertices in any of the k sets, admits a PTAS for trees. Remarkably, the computed cut-size is no larger than that of an optimal balanced solution. In the nal section of our paper, we harness results on embedding graph metrics into tree metrics to extend our PTAS for trees to general graphs. In addition to being conceptually simpler and easier to analyse, our scheme improves the best factor known on the cut-size of near-balanced solutions from O(log1:5 n="2) [Andreev and R acke TCS 2006] to O(log n), for weighted graphs. This also settles a question posed by Andreev and R acke of whether an algorithm with approximation guarantees on the cut-size independent from " exists.