Graphpartitionierung

Graphpartitionierung bezeichnet die Zerlegung der Knotenmenge eines Graphen G=(V,E) in k disjunkte Teilmengen V1,...,Vk mit der Eigenschaft, dass der Schnitt der Teilmengen durch Kanten möglichst klein ist und die Teilmengen typischerweise balanciert sind (|Vi| ≈ |V|/k). Typisches Ziel ist die Minimierung der Anzahl oder des Gesamtgewichts der Kanten, die zwei Partitionen trennen, oft verbunden mit Nebenbedingungen zur Gleichverteilung der Kanten- oder Knotenlast in den Teilgraphen. In vielen Anwendungen wird zusätzlich die Qualität der Verteilung innerhalb der Partitionen berücksichtigt oder die Kantenlastrichtung in gerichteten Graphen beachtet.

Es gibt verschiedene Varianten und Erweiterungen. Unterscheidungen treffen sich nach Gewichtung (gewichtete Graphen), Richtung der Kanten (gerichtete Graphen) sowie nach der Struktur der Teilung (k-Weg-Partitionierung, unbalancierte Partitionierung). Hypergraph-Partitionierung generalisiert das Problem durch Hyperkanten, die mehrere Teilmengen verbinden; diese Form ist besonders in VLSI-Design und in der Zerlegung von Matrizenbänken relevant.

Das Problem ist NP-hart, insbesondere für k≥2. Für kleine Graphen oder präzise Anforderungen kommen exakte Verfahren (z. B. Branch-and-Bound oder Integer-Programming) zum Einsatz, meist mit begrenzter Skalierbarkeit. Praktisch dominieren heuristische und approximate Verfahren: Multilevel-Graph-Partitionierung (Kohärenz durch Abkoppeln, Grob-/Fein-Phasen), exemplifiziert durch Tools wie METIS, Scotch oder KaHIP; lokale Suchverfahren wie Kernighan–Lin oder Fiduccia–Mattheyses; sowie spektrale Methoden, die den Laplace-Betweenness-Eigenvektor verwenden.

Anwendungsgebiete umfassen die Lastverteilung in parallelen Computersystemen, Minimierung von Kommunikationsvolumen, VLSI-Layout, Matrixfaktorisierung und Netzwerk- sowie Clustering-Aufgaben.

---