Tight bounds for the min-max boundary decomposition cost of weighted graphs

SPAA 2006.



Many load balancing problems that arise in scientific computing applications boil down to the problem of partitioning a graph with weights on the vertices and costs on the edges into a given number of equally-weighted parts such that the maximum boundary cost over all parts is small.

Here, this partitioning problem is considered for graphs G=(V,E)G=(V,E) with edge costs c ⁣:ER0c\colon E\to \mathbb R_{\ge 0}, that have bounded maximum degree and a pp-separator theorem for some p>1p>1, i.e., any (arbitrarily weighted) subgraph of GG can be separated into two parts of roughly the same weight by removing a separator SVS\subseteq V such that the edges incident to SS in the subgraph have total cost at most proportional to (ecep)1/p(\sum_e c^p_e)^{1/p}, where the sum is over all edges in the subgraph.

For arbitrary weights w ⁣:VR0w\colon V\to \mathbb R_{\ge 0}, we show that the vertices of such graphs can be partitioned into kk parts such that the weight of each part differs from the average weight vVwv/k\sum_{v\in V}w_v/k by at most (11k)maxvVwv(1-\frac{1}{k})\max_{v\in V}w_v, and the boundary edges of each part have total cost at most proportional to (eEcep/k)1/p+maxeEce(\sum_{e\in E}c_e^p/k)^{1/p}+\max_{e\in E}c_e. The partition can be computed in time nearly proportional to the time for computing separators SS for GG as above.

Our upper bound is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has c1c\equiv 1, w1w\equiv 1, and one allows parts of weight as large as a constant multiple of the average weight.

We also give a separator theorem for dd-dimensional grid graphs with arbitrary edge costs, which is the first result of its kind for non-planar graphs.