Intuitive Strategien zur Lösung von Graph- und Erfüllbarkeitsproblemen
Final Report Abstract
Wenn wir davon ausgehen, daß die weit verbreitete Annahme P≠NP gilt, so können viele wichtige Probleme nicht in polynomieller Zeit gelöst werden. Allerdings gibt es verschiedene Ansätze, dennoch exakte Lösungen für solche Probleme zu berechnen. Besonders hervorzuheben sind hier die Algorithmen mit moderater exponentieller Laufzeit und Algorithmen aus dem Gebiet der parametrisierten Komplexität. In diesem Projekt untersuchten wir möglichst intuitive Algorithmen, welche in der Regel aus einem der beiden oben genannten Gebieten stammen. Die Grundeigenschaft von intuitiven Algorithmen ist dabei, daß sie einer einfachen Grundidee folgen sollen und möglichst wenig Overhead enthalten sollen. Gleichzeitig sollen sie aber Probleme in relativ geringer Zeit exakt lösen. Die geforderte Einfachheit ist bei letzterem Aspekt natürlich ein Nachteil, zumindest wenn wir Algorithmen in Bezug auf ihre theoretischen Schranken hin analysieren. Dies muss meist durch eine deutlich aufwendigere Analyse ausgeglichen werden. So mußten wir zum Beispiel die Measure&Conquer Methode auf parametrisierte Probleme anpassen oder aber einen computerunterstützten Beweis zur Hilfe ziehen. Allerdings gibt es mehrere Aspekte von intuitiven Algorithmen, die diesen Nachteil ausgleichen. Zum einen ist die Laufzeit von intuitiven Algorithmen, sei sie im Allgemeinen auch höher als die von komplizierteren Algorithmen, zumindest auf kleinen Instanzen oft konkurrenzfähig. Auf größeren Instanzen übersteigt aber auch die Laufzeit von komplizierteren Algorithmen jegliche sinnvollen Werte, so daß intuitive Algorithmen in den meisten relevanten Fällen dennoch zu bevorzugen sind. Zudem lassen sich intuitive Algorithmen oft deutlich leichter implementieren, da in theoretischen Algorithmen oft sehr komplexe Operationen versteckt sind. Schließlich sind intuitive Algorithmen aber auch ästhetisch zu bevorzugen. Komplizierte Algorithmen sind oft nur deshalb kompliziert, um ihre theoretische Analyse zu vereinfachen oder erst zu ermöglichen. Die zusätzliche Komplexität verrät uns daher oft nur, daß unsere Analysewerkzeuge unzureichend sind, und liefert uns wenig Information darüber, worin die Schwierigkeit des Problems selbst liegt. Oft gelang es uns aber im Rahmen des Projekts sogar, intuitive Algorithmen zu entwickeln, die herkömmlichen Algorithmen auch in Hinsicht auf eine traditionelle Worst-Case Analyse überlegen sind. Unter anderem untersuchten wir im Rahmen des Projektes die folgenden Probleme: - Basierend auf oberen Schranken für die Baumweite von Graphen, fanden wir Algorithmen für Max-2-SAT und MaxCut mit einer Laufzeit von O*(1.128m). Hierbei bezeichnet m die Anzahl der Klauseln der Formel bzw. die Anzahl der Kanten eines Graphen. - Im Falle von Maximum Leaf Spanning Tree, konstruierten wir einen parametrisierten Algorithmus mit einer Laufzeit von O*(4k), der nicht auf ungerichteten, sondern auch auf gerichteten Graphen eine Lösung findet. - Für Partial Vertex Cover entwarfen wir einen intuitiven Algorithmus, dessen Laufzeit durch O*(1.396t) beschränkt ist. Außerdem entwickeln wir einen auf diesem Algorithmus basierenden randomisierten Algorithmus mit einer Laufzeit von O*(1.2993t). - Weiterhin zeigten wir, daß Partial Dominating Set mit einer Laufzeit von von O*(4 + εt) gelöst werden kann. - Für das Irredundant Set Problem konnten wir mittels eines intuitiven Algorithmus als erste die triviale Schranke von O*(2|V|) verbessern. - Schließlich entwarfen wir einen intuitiven Algorithmus für Independent Set mit einer Laufzeit von O*(1.2132|V|).
Publications
- Intuitive algorithms and t-vertex cover. In: Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), number 4288 in Lecture Notes in Computer Science, pages 598– 607. Springer, 2006
J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
- Partial vs. complete domination: t-dominating set. In: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), number 4362 in Lecture Notes in Computer Science, pages 367–376. Springer, 2007
J. Kneis, D. Mölle, and P. Rossmanith
- A new algorithm for finding trees with many leaves. In: Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), number 5369 in Lecture Notes in Computer Science, pages 270– 281. Springer, 2008
J. Kneis, A. Langer, and P. Rossmanith
- Improved upper bounds for partial vertex cover. In: Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), number 5344 in Lecture Notes in Computer Science, pages 240–251. Springer, 2008
J. Kneis, A. Langer, and P. Rossmanith
- A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM Journal on Discrete Mathematics, 23(1):407– 427, 2009
J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
- A fine-grained analysis of a simple independent set algorithm. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), volume 4 of Leibniz International Proceedings in Informatics (LI- PIcs), pages 287–298, 2009
Joachim Kneis, Alexander Langer, and Peter Rossmanith
- An exact algorithm for the maximum leaf spanning tree problem. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC), number 5917 in Lecture Notes in Computer Science, pages 161–172. Springer, 2009
Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, and Peter Rossmanith
- A parameterized route to exact puzzles: Breaking the 2-barrier for irredundance. In: Proceedings of the 7th Italian Conference on Algorithms and Complexity, number 6078 in Lecture Notes in Computer Science, pages 311–322. Springer, 2010
Daniel Binkele-Raible, Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, and Peter Rossmanith
