Partitioning graphs into balanced components

ABSTRACT

We consider the k-balanced partitioning problem, where the goal is to partition the vertices of an input graph G into k equally sized components, while minimizing the total weight of the edges connecting different components. We allow k to be part of the input and denote the cardinality of the vertex set by n. This problem is a natural and important generalization of well-known graph partitioning problems, including minimum bisection and minimum balanced cut.

We present a (bi-criteria) approximation algorithm achieving an approximation of O(√log n log k), which matches or improves over previous algorithms for all relevant values of k. Our algorithm uses a semidefinite relaxation which combines l²₂ metrics with spreading metrics. Surprisingly, we show that the integrality gap of the semidefinite relaxation is Ω(log k) even for large values of k (e.g., k = n^Ω(1), implying that the dependence on k of the approximation factor is necessary. This is in contrast to previous approximation algorithms for k-balanced partitioning, which are based on linear programming relaxations and their approximation factor is independent of k.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: Konstantin Andreev , Harald Racke, Balanced Graph Partitioning, Theory of Computing Systems, v.39 n.6, p.929-939, November 2006 [doi>10.1007/s00224-006-1350-7]
• 3: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 4: Moses Charikar , Mohammad Taghi Hajiaghayi , Howard Karloff , Satish Rao, l²₂ spreading metrics for vertex ordering problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1018-1027, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109670]
• 5: Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 6: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 7: Eden Chlamtac , Konstantin Makarychev , Yury Makarychev, How to Play Unique Games Using Embeddings, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.687-696, October 21-24, 2006 [doi>10.1109/FOCS.2006.36]
• 8: Nikhil R. Devanur , Subhash A. Khot , Rishi Saket , Nisheeth K. Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132594]
• 9: Guy Even, Fast Approximate Graph Partitioning Algorithms, SIAM Journal on Computing, v.28 n.6, p.2187-2214, Dec. 1999 [doi>10.1137/S0097539796308217]
• 10: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 11: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 12: Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Review, v.48 n.1, p.99-130, 2006 [doi>10.1137/050640904]
• 13: U. Feige and J. R. Lee. An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett., 101(1):26--29, 2007.
• 14: M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoret. Comput. Sci., 1(3):237--267, 1976.
• 15: L. Holst and S. Janson. Poisson approximation using the stein-chen method and coupling: number of exceedances of gaussian random variables. Ann. Probab., 18:713--723, 1990.
• 16: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 17: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 18: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 19: Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109669]
• 20: James R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 21: F. Leighton, F. Makedon, and S. Tragoudas. Approximation algorithms for VLSI partition problems. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 2865--2868. IEEE Computer Society Press, 1990.
• 22: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 23: Harald Räcke, Optimal hierarchical decompositions for congestion minimization in networks, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374415]
• 24: 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]
• 25: B. Yu , J. Cheriyan , P. E. Haxell, Hypercubes and Multicommodity Flows, SIAM Journal on Discrete Mathematics, v.10 n.2, p.190-200, May 1997 [doi>10.1137/S089548019426560X]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms