Algorithm Engineering für Graphpartitionierung

• Antragstellerinnen / Antragsteller: Professor Dr. Peter Sanders; Professor Dr. Christian Schulz; Professorin Dr. Dorothea Wagner
• Fachliche Zuordnung: Theoretische Informatik ; Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik ; Softwaretechnik und Programmiersprachen
• Förderung: Förderung von 2010 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 183646693

Graphpartitionierung ist ein wichtiges Werkzeug um große Graphen zu verarbeiten. Diese Graphen stammen häufig aus Anwendungen wie der Finiten Element Methode, der Routenplanung oder aus sozialen Netzwerken. Oft muss die Knotenmenge solcher Graphen partitioniert (oder geclustert) werden, so dass möglichst wenige Kanten zwischen den Blöcken verlaufen. Wenn man z.B. einen Graphen auf k Prozessoren verarbeiten möchte, so möchte man diesen in k ungefähr gleich große Blöcke aufteilen und zwar so das möglichst wenig Interaktion zwischen den Blöcken stattfindet.In der ersten Förderperiode war unser Projekt sehr erfolgreich. Unser primäres Ziel war es das volle Potenzial des Mehrlevel-Ansatzes für Graphpartitionierung und damit verwandte Probleme auszuschöpfen. Wir wollten insbesondere ein besseres Verständnis des Verfahrens erlangen und gleichzeitig jede Komponente verbessern, wie z.B. Kontraktion inklusive Kantenbewertungen und Matchingsalgorithmen, initiales Partitionieren und lokale Suchen. Darauf aufbauend entwickelten wir neue Techniken wie z.B. Metaheuristiken. Ein praktisches Ergebnis unser Arbeiten ist Software, die weltweit in einigen wichtigen Aspekten führend ist. Genauer gesagt liefert die Software die besten Partitionen für fast alle Instanzen aus dem Walshaw Benchmark. Insgesamt erzielten wir leistungsfähigere Algorithmen für Graphenclusterung und Graphpartitionierung. Die erfolgreichsten Implementierungen haben wir als einfach zu bedienende Open-Source-Software veröffentlicht.In der nächsten Projektphase möchten wir den Erfolg der vorherigen Förderperiode auf allgemeinere Probleme und ihre Anwendungen erweitern. Balancierte Graphpartitionierung mit dem Ziel der Schnittminierung ist nur die Spitze des Eisbergs. Viele verwandte Probleme wurden weniger intensiv untersucht, haben aber mindestens genauso viele Anwendungen. Wir erwarten das uns viele der Ansätze die wir für das Basisproblem entwickelt behilflich sein werden, gehen aber auch davon aus das viele neue Fragestellungen und Schwierigkeiten auftauchen werden.Wenn wir zum Beispiel Hypergraphen partitionieren möchten, dann kann man die Basisansätze zwar übertragen, hat dann aber mindestens zwei verschiedene Zielfunktionen und ohne weitere Ideen erhöht sich die Laufzeit dramatisch. Weitere Verallgemeinerungen sind z.B. mehrere Zielfunktionen oder auch sich über die Zeit verändernde Graphen. Andererseits ist es auch wichtig sich Graphfamilien mit speziellen strukturellen Eigenschaften anzuschauen, die es uns erlauben bessere Lösungen effizienter zu berechnen. Zuletzt möchten wir uns mit Parallelisierungen beschäftigen. Dabei interessieren uns sowohl shared-memory parallele Algorithmen, die die heutige zur Verfügung stehende Hardware besser ausnutzen, als auch Parallelisierungen die auf den größten existierenden Supercomputern skalieren. Wie in der vorangegangenen Förderperiode werden wir die erfolgreichsten Implementierungen als Open-Source-Software veröffentlichen.

• DFG-Verfahren: Sachbeihilfen