Graph partition
From Wikipedia, the free encyclopedia
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) V1, V2, ... Vk 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 ε in the part sizes is usually allowed, and the balance criterion is 
.
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.
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.
