Iterative Kompression zur Lösung schwieriger Netzprobleme
Final Report Abstract
Bei Projektabschluss war iterative Kompression als eine wichtige Technik zur effektiven Entwicklung parametrisierter Algorithmen in der Forschungslandschaft allgemein anerkannt. Sie gehört nun (trotz ihrer kurzen Existenz seit 2004) in das Standardrepertoire jedes Forschers im Gebiet der parametrisierten Algorithmik. Dazu haben die Ergebnisse unseres Projekts mit beigetragen. Bemerkenswert ist, dass die iterative Kompression wie wohl (fast) keine andere algorithmische Methode zu jüngsten Durchbrüchen in der Welt der parametrisierten Komplexität führte; das heißt genauer, dass mit Hilfe der iterativen Kompression bis dato bzgl. ihrer parametrisierten Komplexität nicht eingeordnete Probleme als Element der Komplexitätsklasse FPT nachgewiesen werden konnten. Auf Basis dieser und unserer weiteren Projektergebnisse ist zu erwarten, dass die iterative Kompression auch in Zukunft eine wichtige Rolle mindestens in der parametrisierten Algorithmik spielen wird. Unsere nunmehr umfangreichen Erfahrungen mit iterativer Kompression legen aber auch nahe, dass diese Technik vielleicht (noch) nicht so universell einsetzbar ist wie es z.B. die Techniken der Datenreduktion (vermöge in Polynomzeit ausführbarer Reduktionsregeln) oder der tiefenbeschränkten Suchbäume sind. Die für den Erfolg der iterativen Kompression zentral wichtige Entwicklung einer effektiven Kompressionsroutine ist fast immer algorithmisch anspruchsvoll und scheint manchmal gar außer Reichweite (z.B. wegen NP-Schwere des Kompressionsproblems). Darüberhinaus ist nicht für alle Probleme klar, wie selbst der in der Iteration steckende, scheinbar klare Prozess des induktiven Lösungsaufbaus immer funktionieren soll. Eine wichtige, zentral ausgenutzte Eigenschaft bei Algorithmen der iterativen Kompression ist nämlich, dass man davon ausgeht, dass bei „vergrößerten Eingabeinstanzen" (wie z.B. durch schrittweise Knoten- oder Kantenhinzufügung) auch die Lösungsgröße monoton wächst - diese Eigenschaft besitzen aber nicht alle NP-schweren Probleme. Vielleicht ist hier eine kompliziertere, nicht nur „lineare" Induktionsstruktur nötig. Momentan sind uns hierzu aber keine Ansätze bekannt. Eine weitere, wünschenswerte Überraschung wäre die Entwicklung effizienter „Partitionierungstechniken" (Teil der Kompressionsroutine), die bei Parameter k bislang fast immer zu einer unteren exponentiellen Schranke von 2k für die Kompressionsroutine und damit für den Gesamtalgorithmus führen. Positiv überraschend war im Verlaufe des Projekts, dass sich die iterative Kompression nicht nur als Klassifizierungswerkzeug hervorragend bewährt hat, sondern in manchen Fällen ziemlich direkt zu wirklich praktisch wertvollen Algorithmen führte. Zuletzt ist noch positiv zu vermelden, dass die iterative Kompression nicht nur zur Lösung schwerer Netzwerkprobleme einsetzbar ist. Das jüngste Ergebnis von Razgon und O'Sullivan für ALMOST 2-SAT zeigte erstmals, dass auch andere NP-schwere Probleme erfolgreich mit ihr angegangen werden können. Es bleibt zu hoffen, dass in vielen Fällen (wie auch letztgenanntem) für den Praxiseinsatz noch benötigte Beschleunigungen in den nächsten Jahren entwickelt werden können.
Publications
-
Parameterized complexity of finding regular induced subgraphs. In: Proceedings of the 2nd Algorithms and Complexity in Durham (ACID '06) Workshop, volume 7 of Texts in Algorithmics, pages 107-118. College Publications, 2006
H. Moser and D. M. Thilikos
-
Feedback arc set in bipartite tournaments is NP-complete. Information Processing Letters, 102(2-3):62-65, 2007
J. Quo, F. Hüffner, and H. Moser
-
Isolation concepts for enumerating dense subgraphs. In: Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON '07), volume 4598 of Leetore Notes in Computer Science, pages 140-150. Springer, 2007
C. Komusiewicz, F. Hüffner, H. Moser, and R. Niedermeier
-
Optimal edge deletions for signed graph balancing. In: Proceedinigs of the 6th International Workshop on Experimental and Efficient Algorithms (WEA '07), volume 4525 of Lecture Notes in Computer Science, pages 297-310. Springer, 2007
F. Hüffner, N. Betzler, and R. Niedermeier
-
The parameterized complexity of the induced matching problem in planar graphs. In: Proceedings of the 1st International Frontiers of Algorithmics Workshop (FAW '07), volume 4613 of Lecture Notes in Computer Science, pages 325-336. Springer, 2007
H. Moser and S. Sikdar
-
The parameterized complexity of the unique coverage problem. In: Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC '07), volume 4835 of Lecture Notes in Computer Science, pages 621-631. Springer, 2007
H. Moser, V. Raman, and S. Sikdar
-
Enumerating isolated cliques in financial and synthetic networks. In: Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 'O8), Lecture Notes in Computer Science. Springer, 2008
F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier
-
Fixed-parameter algorithms for cluster vertex deletion. In: Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN W), volume 4957 of Lecture Notes in Computer Science, pages 711-722. Springer, 2008
F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier
