Algorithm to Partition Graph into groups

Question

I'm looking for an algorithm to partition a graph into groups of vertices (each of which is connected if it were own graph) of maximum size n while keeping the number of groups minimized. I need this algorithm to partition a delaunay triangulation into regions with equal number of vertices in each region. If anyone has a better idea for tackling this problem, let me know!

Answer 1

It seems you're looking for a solution to the uniform k-way graph partitioning problem, where, given a graph G(V,E), the goal is to partition the vertex-set V into a series of k disjoint subsets V1, V2, ..., Vk such that the size of each subset Vi is approximately |V|/k. Additionally, it's typical to require "nice" partitions, where the sum of the edge weights between any two subsets Vi and Vj is minimised.

Firstly, it's well known that this problem is NP-complete, precluding the existence of efficient exact algorithms. On the up side, a number of effective heuristics have been developed that perform pretty well on many practical problems.

Specifically, schemes based on an iterative multi-level approach have been very successful in practice. In such methods, a hierarchy of graphs is created by incrementally merging adjacent vertices to form a smaller "coarse" graph at each level of the hierarchy. An initial partition is formed when the coarse graph becomes small enough, with this partition then "mapped" back down the hierarchy onto the original graph. An iterative refinement of the partition is typically performed as part of this mapping process, generally leading to pseudo-optimal partitions.

The implementation of such algorithms is non-trivial, but a number of existing packages support such routines. Specifically, the METIS package is used extensively.