Graph partition

The graph partitioning problem in mathematics consists of dividing a graph into pieces, such that the pieces are of about the same size and there are few connections between the pieces.

Consider a graph $G(V,E)$, where "V" denotes the set of vertices and "E" the set of edges. The standard (unweighted) version of the graph partition problem is: Given "G" and an integer "k" >1, partition "V" into "k" parts (subsets) "V₁", "V₂", ... "V_k" such that the parts are disjoint and have equal size, and the number of edges with endpoints in different parts is minimized. In practical applications, a small imbalance $epsilon$ in the part sizes is usually allowed, and the balance criterion is $max\_i\; |V\_i|\; le\; (1+epsilon)\; |V|/k$.

In the general (weighted) version, both vertices and edges can be weighted. The graph partitioning problem then consists of dividing "G" into "k" disjoint parts such that the parts have approximately equal weight and the size of the edge cuts is minimized. The size of a cut is the sum of the weights of the edges contained in it, while the weight of a part is the sum of the weights of the vertices in the part. When k=2 the problem is also referred to as the Graph Bisection Problem.

A common extension is to hypergraphs, where an edge can connect more than two vertices. A hyperedge is not cut if all vertices are in one partition, and cut exactly once otherwise, no matter how many vertices are on each side. This usage is common in Electronic design automation.

Graph partitioning is known to be NP-complete, but can be solved in polynomial time for |Vi|=2 by matching (see Michael R. Garey and David S. Johnson. Computers and Intractability ; A Guide to the Theory of NP-Completeness, page 209). Fast heuristics work well in practice. An important application of graph partitioning is load balancing for parallel computing, where each vertex corresponds to a computational task and the edges correspond to data dependencies. A more general model, hypergraph partitioning, is now often preferred. Software for graph partitioning is widely available.

Bibliography

cite journal |title=An efficient heuristic procedure for partitioning graphs |url=http://www.ece.wisc.edu/~adavoodi/teaching/756/papers/kl.pdf |author=BW Kernighan, S Lin |journal=Bell System Technical Journal |year=1970 One of the early fundamental works in the field. However, performance is O(N^2), so it is no longer commonly used.

cite conference |title=A Linear-Time Heuristic for Improving Network Partitions |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1585498 |author=CM Fiduccia, RM Mattheyses |booktitle=Design Automation Conference |year1982 A later variant that is linear time, very commonly used, both by itself and as part of multilevel partitioning, see below.

cite journal |title=A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs |url=http://glaros.dtc.umn.edu/gkhome/node/107 |author= G Karypis, V Kumar |journal=Siam Journal on Scientific Computing |year=1999 Multi-level partitioning is the current state of the art. This paper also has good explanations of many other methods, and comparisons of the various methods on a wide variety of problems.

cite journal |title=Multilevel hypergraph partitioning: applications in VLSI domain |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=748202 |author= Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |date=Mar 1999 |volume=7 |issue=1 |pages=pp. 69–79 |doi=10.1109/92.748202 Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design.

cite journal |title=Optimization by Simulated Annealing |url=http://www.sciencemag.org/cgi/content/abstract/220/4598/671 |author=S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi |journal=Science |date=13 May 1983 |issue=4598 |pages=671–680 |doi= 10.1126/science.220.4598.671 |volume=220 |pmid=17813860 Simulated annealing can be used as well.

cite journal |title=New spectral methods for ratio cut partitioning and clustering |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=159993 |author=Hagen, L. and Kahng, A.B. |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |date=Sept 1992 |volume=11, |issue=9 |pages= 1074–1085 |doi=10.1109/43.159993. There is a whole class of "spectral partitioning" methods, which use the Eigenvectors of the Laplacian of the connectivity graph. You can see [http://www.stanford.edu/~dgleich/demos/matlab/spectral/spectral.html a demo of this] , using Matlab.