Tight bounds for the Min-Max boundary decomposition cost of weighted graphs

ABSTRACT

Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of almost equally-weighted parts such that the maximum boundary cost over all parts is small.Here, this partitioning problem is considered for boundeddegree graphs G ≡ (V,E) with edge costs c: E → R₊ that have a p-separator theorem for some p > 1, i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts of roughly the same weight by removing separator S⊆V such that the edges incident to S in the subgraph have total cost at most proportional to (Ε_ecp<over>e)^1/p, where the sum is over all edges in the subgraph.We show for all positive integers k and weights w that the vertices of G can be partitioned into k parts such that the weight of each part differs from the average weight Ε_v∈V w_v<over>k by less than max_v∈V w_v, and the boundary edges of each part have cost at most proportional to (Εe∈ cp<over>e/k)^1/p + max_e∈E c_e. The partition can be computed in time nearly proportional to the time for computing a separator S of G.Our upper bound on the boundary costs 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 c ≡ 1, w ≡ 1, and one allows parts with weight exceeding the average by a constant fraction.

REFERENCES

• 1: N. Alon , P. Seymour , R. Thomas, A separator theorem for graphs with an excluded minor and its applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.293-299, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100254]
• 2: H. Djidjev. Partitioning planar graphs with vertex costs: Algorithms and applications. Algorithmica, 28(1):51--75, 2000.
• 3: Marcos Kiwi , Daniel A. Spielman , Shang-Hua Teng, Min—max-boundary domain decomposition, Theoretical Computer Science, v.261 n.2, p.253-266, June 28, 2001 [doi>10.1016/S0304-3975(00)00143-2]
• 4: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.
• 5: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 6: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
• 7: Horst D. Simon , Shang-Hua Teng, How Good is Recursive Bisection?, SIAM Journal on Scientific Computing, v.18 n.5, p.1436-1445, Sept. 1997 [doi>10.1137/S1064827593255135]
• 8: D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996
• 9: D. Steurer. Tight bounds on the min-max boundary decomposition cost of weighted graphs. arXiv, cs.DS/0606001, 2006.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
graph partitioning, graph separators, load balancing, parallel computing, scheduling