Graph partitioning and disturbed diffusion

The NP-hard graph partitioning problem is an important subtask in load balancing and many other applications. It requires the division of a graph's vertex set into P equally sized subsets such that some objective function is optimized. State-of-the-art libraries addressing this problem show several deficiencies: they are hard to parallelize, focus on small edge-cuts instead of few boundary vertices, and often produce disconnected partitions. This work introduces our novel graph partitioning and repartitioning heuristic BUBBLE-FOS/C. In contrast to other libraries, BUBBLE-FOS/C does not try to minimize the edge-cut explicitly, but focuses instead implicitly on good partition shapes. The shapes are optimized by diffusion processes that are embedded into an iterative framework. This approach incorporates a high degree of parallelism. B esides describing the evolution process that led to the new diffusion scheme FOS/C used by BUBBLE-FOS/C, we reveal some of FOS/C's properties and propose a number of enhancements for a fast and reliable implementation. Our experiments, in which we compare sequential and parallel BUBBLE-FOS/C implementations to the state-of-the-art libraries METIS and JOSTLE, reveal that our new heuristic is slower, but generates high-quality solutions that are often superior. (C) 2009 Elsevier B.V. All rights reserved.