Ein Graph ist eine Menge von Knoten und Kanten zwischen diesen Knoten. Man unterscheidet zwischen gerichteten Graphen, wo Einbahnstraßen darstellbar sind, oder den ungerichteten Graphen, wo Beziehungen zwischen zwei Knoten immer beidseitig sind. Beispiele sind die graphische Darstellung von Beziehungen in einem sozialen Netz oder Straßennetze, für deren Verarbeitung das Forschungsgebiet von Christian Schulz immer bedeutender wird, wie wir in seinem Gespräch mit Gudrun Thäter erfahren.

Eine wichtige Aufgabe im Umgang mit Graphen ist die Aufteilung (oder fachsprachlich Partitionierung), von Graphen in kleinere Teile. Dies kommt z.B. der Parallelisierung der Arbeit auf den Graphen zugute, und ist unumgänglich, wenn Graphen eine Größe haben, die nicht mehr von einem Prozessor bearbeitet werden kann. Ein wichtiges Merkmal ist hier, die Aufteilung möglichst gleichmäßig vorzunehmen, damit die Aufteilung von z.B. Rechenzeit gleichmäßig erfolgt, und gleichzeitig wenig Kommunikation zwischen der Bearbeitung der Einzelteile erforderlich ist. Es geht um eine möglichst gute Skalierbarkeit der Graphverarbeitung.

Ein wichtiges Anwendungsproblem ist die Routenplanung, bei der zwischen zwei Punkten auf der Erde die zeitlich kürzeste Verbindung berechnet werden soll. In der Informatik ist der Dijkstra-Algorithmus der passende Basis-Algorithmus für diese Aufgabe, doch er ist für große Graphen in seiner ursprünglichen Form sehr ineffizient. In Kombination mit einer passenden Graphpartitionierung und Algorithmen kann man das Verfahren deutlich effizienter ausführen und beschleunigen.

Ein klassisches Verfahren zur Aufteilung ist das Mehrschichtverfahren über die Laplace-Matrix, wo ausgenutzt wird, dass zwischen den Eigenwerten der Matrix und der Schnittstruktur des Graphen enge Zusammenhänge bestehen. Dieses Verfahren wurde zum Mehrschichtverfahren für Graphen weiterentwickelt, bei dem in einer sogenannten Kontraktion benachbarte Knoten und parallele Kanten jeweils zusammengeführt werden, und der Graph zu einem kleinen und kantengewichteten Graph vereinfacht wird. Schließlich wird das Problem auf einem vereinfachten, groben Gitter gelöst, und dann jeweils mit lokalen Suchen auf feinere Graphen erweitert. Für die Kontraktion werden Heuristiken und Kantenbewertungsfunktionen verwendet.

Ein weiterer Ansatz sind auch evolutionäre Algorithmen. Dabei wurde eine allgemeinere Umgebung geschaffen, die auf eine weite Klasse von Optimierungsproblemen angewendet werden kann.

Die Graphentheorie ist natürlich auch Teil der diskreten Mathematik, und besonders berühmt ist auch das Traveling Salesperson Problem. Gleichzeitig ist das Thema aber auch in der Theoretischen Informatik, im Algorithm Engineering und in der Software-Entwicklung beheimatet.

Literatur und Zusatzinformationen

• C. Schulz: High Quality Graph Partitioning, PhD thesis. Karlsruhe Institute of Technology, 2013.
• P. Sanders, C. Schulz: Distributed Evolutionary Graph Partitioning, Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX'12), pages 16--19, 2012.
• P. Sanders, C. Schulz: High Quality Graph Partitioning, Proceedings of the 10th DIMACS Implementation Challenge Workshop: Graph Partitioning and Graph Clustering, pages 1--17, AMS, 2013.
• P. Sanders, C. Schulz: Think Locally, Act Globally: Highly Balanced Graph Partitioning, proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of LNCS, pages 164--175, 2013.
• R. Glantz, H. Meyerhenke, C. Schulz: Tree-based Coarsening and Partitioning of Complex Networks, Technical Report, Karlsruhe Institute of Technology, 2014.
• KaHIP Homepage
• KaHIP auf Twitter
• Christian Schulz auf Twitter
• Podcast: Death of a traveling salesman