Tight bounds for the min-max boundary decomposition cost of weighted graphs
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 with edge costs , that have bounded maximum degree and a -separator theorem for some , i.e., any (arbitrarily weighted) subgraph of can be separated into two parts of roughly the same weight by removing a separator such that the edges incident to in the subgraph have total cost at most proportional to , where the sum is over all edges in the subgraph.
For arbitrary weights , we show that the vertices of such graphs can be partitioned into parts such that the weight of each part differs from the average weight by at most , and the boundary edges of each part have total cost at most proportional to . The partition can be computed in time nearly proportional to the time for computing separators for 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 , , and one allows parts of weight as large as a constant multiple of the average weight.
We also give a separator theorem for -dimensional grid graphs with arbitrary edge costs, which is the first result of its kind for non-planar graphs.