ABSTRACT
In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υ • n<over>k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2.
- Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In 27th Annual ACM Symposium on the Theory of Computing, pages 284--293, 1995. Google ScholarDigital Library
- Even, Naor, Rao, and Schieber. Fast approximate graph partitioning algorithms. SIAM Journal of Computing, 28(6):2187--2214, 1999. Google ScholarDigital Library
- Guy Even, Joseph Naor, Satish Rao, and Baruch Schieber. Divide-and-conquer approximation algorithms using spreading metrics. Journal of the ACM(JACM), 47(4):585--616, 2000. Google ScholarDigital Library
- U. Feige, R. Krauthgamer, and K. Nissim. Approximating the minimum bisection size. In 32nd Annual ACM Symposium on the Theory of Computing, pages 530--536, 2000. Google ScholarDigital Library
- Uriel Feige and Robert Krauthgamer. A polylogarithmic approximation of the minimum bisection. SIAM Journal on Computing, 31(4):1090--1118, 2002. Google ScholarDigital Library
- C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In 19th IEEE Design Automation Conference, pages 175--181, 1982. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co, San Francisco, CA, 1979. Google ScholarDigital Library
- D. Hochbaum and D. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM Journal on Computing, 17(3):539--551, 1988. Google ScholarDigital Library
- B.W. Kernighan and S. Lin. An efficient heuristic for partitioning graphs. Bell Sys. Tech. Journal, 49:291--308, 1970.Google Scholar
- T. Leighton, F. Makedon, and S. Tragoudas. Approximation algorithms for vlsi partition problems. In IEEE International Symposium on Circuits and Systems, (ISCAS '90), volume 4, pages 2865--2868, 1990.Google ScholarCross Ref
- T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM(JACM), 46(6):787--832, 1999. Google ScholarDigital Library
- Huzur Saran and Vijay V. Vazirani. Finding k-cuts within twice the optimal. SIAM Journal of Computing, 24(1):101--108, 1995. Google ScholarDigital Library
- Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? SIAM Journal on Scientific Computing, 18(5):1436--1445, 1997. Google ScholarDigital Library
Index Terms
Balanced graph partitioning
Recommendations
Fast Approximate Graph Partitioning Algorithms
We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity $\rho$-separators. A $\rho$-separator is a subset of ...
Partitioning a graph into small pieces with applications to path transversal
Given a graph $$G = (V, E)$$G=(V,E) and an integer $$k \in \mathbb {N}$$kýN, we study $$k$$k-Vertex Separator (resp. $$k$$k-Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in ...
Partitioning of a graph into induced subgraphs not containing prescribed cliques
AbstractLet K p be a complete graph of order p ≥ 2. A K p-free k-coloring of a graph H is a partition of V ( H ) into V 1 , V 2 … , V k such that H [ V i ] does not contain K p for each i ≤ k. In 1977 Borodin and Kostochka conjectured that any graph H ...
Comments