Graphstrukturtheorie und algorithmische Anwendungen
Final Report Abstract
Ein Durchbruch in der modernen Graphentheorie ist Robertsons und Seymours Beweis von Wagners Vermutung. Der in über 20 Veröffentlichungen publizierte Beweis liefert, neben zahlreichen Erkenntnissen über die Struktur von Graphen, die Existenz vieler überraschender Polynomialzeitalgorithmen. Allerdings sind die meisten dieser Algorithmen weit entfernt davon, in der Praxis verwendbar zu sein: Oft führen viel zu große Konstanten zu impraktikablen Rechenzeiten, bzw. geben rein existenzielle Beweismethoden keine konstruktiven Algorithmen an die Hand. Im Projekt GalA haben wir diese Konstanten genauer untersucht, rein existenzielle Aussagen konstruktiv gemacht und die Theorie verfeinert, erweitert und zur Verbesserung von Compilern eingesetzt. Für planare Graphen haben wir den derzeit schnellsten parametrischen Algorithmus für das berühmte disjunkte Pfade-Problem entwickelt. Das Disjunkte-Pfade-Problem ist das algorithmische Problem, für einen gegebenen Graphen G und k Knotenpaare (s 1 , t 1 ), . . . , (s k , t k ) von G zu entscheiden, ob es paarweise knotendisjunkte Pfade P 1 , . . . P k in G gibt, so dass P i die Knoten s i und t i verbindet. Karp hat 1975 gezeigt, dass das Disjunkte-Pfade-Problem NP-schwer ist, und Lynch, dass es auch auf planaren Graphen NP-schwer bleibt. Für festes k ist das Problem in Polynomialzeit lösbar: Robertson und Seymour haben gezeigt, dass es in Zeit f(k) · |V (G)| 3 lösbar ist, womit das Problem auch fixed-parameter tractable ist. Von der Funktion f ist allerdings wenig mehr bekannt, als dass sie berechenbar ist. Unser Algorithmus für das planare Disjunkte-Pfade-Problem hat Laufzeit 2^2O(k) · |V (G)| 2. Damit ist erstmalig die Abhängigkeit von k konkret bestimmt. Er lässt sich kurz beschreiben: Lösche im gegebenen Graphen solange ”irrelevante“ Knoten, bis der verbleibende Graph kleine Baumweite hat (also ”baumä#hnlich“ ist) und löse das Problem anschließend mit dynamischem Programmieren. Der Korrektheitsbeweis dagegen ist aufwändig. Um die Abhängigkeit der Laufzeit von k genau zu bestimmen, haben wir eine neue, elementarere Beweistechnik entwickelt, die unabhängig von Robertsons und Seymours Arbeiten ist. Unsere Methode basiert einzig auf dem ”Gittersatz für Baumweite“. Insbesondere haben wir dabei das Ergebnis der Veröffentlichung Graph Minors XXII für planare Graphen neu und mit beweisbar optimaler Parameterabhängigkeit bewiesen. Es bleibt offen, ob sich die Laufzeit des planaren Disjunkte-Pfade-Problems weiter reduzieren lässt. Wir konnten zeigen, dass dies mit unseren Methoden nicht möglich ist. Motiviert durch den großen Erfolg der sog. Baumzerlegungen – sowohl in Graphentheorie als auch in Algorithmik – haben wir die Struktur von Graphen beschränkter Rangweite genauer untersucht. Die Rangweite ist in bestimmter Hinsicht stärker als die Baumweite, aber bisher weit weniger verstanden. Wir haben uns zunächst auf die Struktur von Graphen beschränkter linearer Rangweite beschränkt. Wir haben die Graphen mit linearer Rangweite höchstens 1 durch verbotene Konfigurationen charakterisiert, gezeigt, dass auf Bäumen (überraschenderweise) Rangweite und Pfadweite übereinstimmen, und anschließend, dass sich die lineare Rangweite von distancehereditary Graphen (Graphen der Rangweite höchstens 1) in Polynomialzeit bestimmen lässt. (Die Bestimmung der Pfadweite dieser Graphen dagegen ist NP-schwer). Zudem haben wir weitere strukturelle Charakterisierungen gegeben. Ein k-strukturiertes Programm ist ein Computerprogramm, dessen Kontrollflussgraph die Baumweite höchstens k hat. In der Praxis sind viele Programme strukturiert, wenn man die Anzahl der gotos beschränkt. In seiner von diesem Projekt finanzierten Dissertation hat Philipp Krause dies genutzt um den ersten exakten Polynomialzeitalgorithmus für das Problem der optimalen Platzierung von Bank-Selection-Instruktionen strukturierter Programme zu entwickeln, Lifetime-optimale Redundanzelimination optimal in Linearzeit zu lösen, sowie auch – für eine feste Registerzahl – das Problem der Registerallokation optimal in Polynomialzeit zu lösen. Der Allokator erlaubt auch die Berücksichtigung von Registeraliasing, Registerpräferenzen, Coalescing, und Optimierung auf verschiedene Ziele wie Codegröße, Geschwindigkeit, Energieverbrauch oder Kombinationen davon und führt u. A. zu Codegrößenreduktionen von bis zu 20%. Diese Algorithmen sind im SDCC, einem 6C-Compiler für eingebettete Systeme, implementiert. Die Implementierungen machen maßgeblich von Baumzerlegungen gebrauch. Wir haben eine umfangreiche, freie Bibliothek mit Algorithmen zur Berechnung von Baumzerlegungen erstellt. Diese ist in der Softwaredistribution SageMath integriert und dient auch als Referenzimplementierung für den 1st Parameterized Algorithms and Computational Experiments Challenge, PACE 2016.
Publications
- Tight bounds for linkages in planar graphs, Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP’11), pp. 110-121, Lecture Notes in Computer Science, 2011
Isolde Adler, Stavros Kolliopoulos, Philipp Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios Thilikos
- Linear Rank-Width and Linear Clique-Width of Trees, Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’13), Lecture Notes in Computer Science, pp. 12-25, 2013
Isolde Adler, Mamadou Kanté
- Optimal Register Allocation in Polynomial Time, Proceedings of the 22nd International Conference on Compiler Construction (CC 2013), pp. 1-20, 2013
Philipp Krause
- Graph-Theoretic Concepts in Computer Science - 40th International Workshop (WG 2014), pp. 42–55, 2014
Isolde Adler, Mamadou Moustapha Kanté, O.-Joung Kwon
(See online at https://dx.doi.org/10.1007/978-3-319-12340-0) - Obstructions for linear rankwidth at most 1, Discrete Applied Mathematics, 168:3–13, 2014
Isolde Adler, Arthur Farley, Andrzej Proskurowski
(See online at https://doi.org/10.1016/j.dam.2013.05.001) - The Complexity of Register Allocation, Discrete Applied Mathematics, 168(0):51–59, 2014
Philipp Krause
(See online at https://doi.org/10.1016/j.dam.2013.03.015)
