Parallel Graph Partitioning is the problem of dividing a graph's vertices into k roughly-equal-sized subsets (partitions) while minimizing the number of edges crossing partition boundaries (the edge cut), which is fundamental to distributing graph computations, mesh decomposition for scientific simulation, and circuit placement. High-quality partitioning directly determines distributed algorithm communication cost.

Graph partitioning is NP-hard in general, but practical multilevel heuristics achieve near-optimal results for most real-world graphs.

Multilevel Partitioning Framework (METIS, ParMETIS, KaHIP):

Coarsening: Heavy-edge matching — greedily match vertices connected by heavy-weight edges and collapse them into single vertices. Each coarsening level roughly halves the graph. Continue until the graph has a few hundred vertices. Alternative: random matching, sorted heavy-edge matching, or algebraic multigrid-inspired coarsening.

Initial Partitioning: On the coarsest graph (small enough for exact or expensive heuristics). Methods: recursive bisection, spectral partitioning, or greedy growing from random seeds.

Refinement: At each uncoarsening level, apply local refinement to improve the cut. Kernighan-Lin (KL) / Fiduccia-Mattheyses (FM) algorithms: iteratively move vertices between partitions to maximize cut reduction while maintaining balance constraints. FM runs in O(|E|) per pass and is the standard refinement algorithm.

Parallel Partitioning Challenges: Distributed graphs may not fit in a single machine's memory. ParMETIS parallelizes each phase: parallel matching for coarsening, parallel refinement with boundary vertex exchange, and parallel initial partitioning. Communication overhead during refinement is proportional to the number of boundary vertices.

Quality Metrics: Edge cut (primary metric — fewer cross-partition edges = less communication); balance (max partition size / average partition size — target <1.03); communication volume (sum of unique boundary vertices per partition — may differ from edge cut for hypergraph/multi-constraint problems); and partition connectivity (number of different partitions each partition communicates with — affects message count).

Applications: Distributed graph processing (each machine processes one partition, communication proportional to edge cut); FEM mesh decomposition (load-balance computation while minimizing inter-processor data exchange); VLSI circuit placement (recursive bisection for min-cut placement); sparse matrix partitioning (row/column reordering for parallel SpMV); and social network analysis (community detection as graph partitioning).

Streaming and Dynamic Partitioning: For graphs too large to load or evolving over time: streaming algorithms assign vertices to partitions as they arrive (hash-based or balanced greedy), and dynamic repartitioning incrementally adjusts partitions as the graph changes.

Graph partitioning is the foundational preprocessing step for virtually all distributed graph computation — the quality of the partition directly determines parallel efficiency, making it one of the most impactful algorithmic choices in large-scale graph processing.