Graph partitioning

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) 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 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

BW Kernighan, S Lin (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal One of the early fundamental works in the field. However, performance is O(N^2), so it is no longer commonly used. CM Fiduccia, RM Mattheyses "A Linear-Time Heuristic for Improving Network Partitions". Design Automation Conference . A later variant that is linear time, very commonly used, both by itself and as part of multilevel partitioning, see below. G Karypis, V Kumar (1999). "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs". Siam Journal on Scientific Computing 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. Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. "Multilevel hypergraph partitioning: applications in VLSI domain". IEEE Transactions on Very Large Scale Integration (VLSI) Systems 7 (1): pp. 69–79. Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design. S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi "Optimization by Simulated Annealing". Science 220 (4598): 671–680. Simulated annealing can be used as well. Hagen, L. and Kahng, A.B. "New spectral methods for ratio cut partitioning and clustering". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11,  (9): 1074–1085. . There is a whole class of spectral partitioning methods, which use the Eigenvectors of the Laplacian of the connectivity graph. You can see a demo of this, using Matlab.

Search another word or see Graph partitioningon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature