Algorithmen mit verfeinerter Worst-Case-Analyse auf der Basis geeigneter Schwierigkeitsbegriffe

• Applicant: Professor Dr. Peter Rossmanith
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5433832

• Final Report Year: 2009

Final Report Abstract

In der theoretischen Informatik wird die Laufzeit von Algorithmen klassischerweise durch eine Worst-Case-Analyse nach oben abgeschätzt. Diese Vorgehensweise ist vielfach bewährt und akzeptiert, liefert jedoch naturgemäß oft eine vergleichsweise pessimistische Einschätzung der Härte eines vorliegenden Problems, wenn wenige schwierige Fälle die obere Schranke für die Laufzeit des Algorithmus bestimmen. Treten solche Fälle in der Praxis nur selten auf, beobachtet man für gewöhnlich einen gewaltigen Unterschied zwischen vor hergesagter und tatsächlicher Laufzeit. Eine Möglichkeit, die Laufzeit von Algorithmen feiner abzuschätzen, bietet die Parametrisierte Komplexitätstheorie: Mit Hilfe eines geeigneten Parameters wird die Laufzeit nun nicht nur wie üblich in der Eingabelänge analysiert, sondern zusätzlich auch in diesem Parameter. Wenn dieser Parameter nun so gewählt wurde, daß er die Schwierigkeit einer vorliegenden Probleminstanz treffend beschreibt, gelingt in vielen Fällen eine feinere Laufzeitanalyse, die der tatsächlichen Laufzeit auf praktischen Instanzen näher kommt. Im vorliegenden Projekt wurden Algorithmen für Entscheidungs- und Optimierungsprobleme entwickelt, deren Laufzeit auf der Basis geeigneter Schwierigkeitsbegriffe möglichst genau analysiert werden sollte. Hierzu wurden zunächst die Probleminstanzen selbst auf die Frage hin untersucht, ob und welche Eigenschaften eines Problems charakteristisch für die Härte einer jeweils vorliegenden Instanz sind. Wenn möglich entwickelten wir unter Ausnutzung dieser Eigenschaften schnellere Algorithmen mit einer entsprechenden mathematischen Laufzeitanalyse. Beispielsweise untersuchten wir das Problem der Dreifärbbarkeit oder des Model-Checkings von MSO-Formeln, der Anwendung von Unique Hitting Set in der Sicherheit von Netzwerken und optimierten die Lösungsverfahren für die Probleme Exact Satisfiabilbity, Power Dominating Set sowie Steiner Tree. In einigen Fällen verlief die Suche nach geeigneten Schwierigkeitsbegriffen (Parametern) leider ergebnislos, beispielsweise im Fall der Dreifärbbarkeit. Für einige Parameter konnten wir sogar Härte im Sinne der parametrisierten Komplexitätstheorie beweisen, etwa bei Power Dominating Set oder Max Exact SAT. Dies bedeutet, daß wahrscheinlich wenig Hoffnung besteht, für diese Schwierigkeitsbegriffe jemals einen Algorithmus zu finden, dessen Laufzeit maßgeblich von diesem Wert der Schwierigkeit beeinflusst wird (genauer, daß das Problem mit diesem Parameter fixed parameter tractable ist). In vielen Fällen konnten wir aber neue und schnellere Algorithmen entwickeln. Im Falle des Steiner Tree-Problems z.B. war der seit 30 Jahren bekannte Dreyfus-Wagner-Algorithmus mit einer Laufzeit von 3'k poly(n) das bis dato komplexitätstheoretisch schnellste bekannte Verfahren. Wir konnten dieses auf (2+ε)^k poly{n) verbessern. Bei einer ganzen Reihe von weitergehenden Veröffentlichungen wird dieses Ergebnis als Baustein für neue Resultate verwendet. Für das aus der Biologie motivierte und in der Bioinformatik wichtige Problem Minimum Quartet Inconsistency entwarfen wir Algorithmen mit Laufzeiten von O(3.0446^k n+n^4), O(2.0162'^k n^3+n^5) sowie sogar 0*((1 + ε)^k) für beliebiges ε > 0. Darüber hinaus entwickelten wir allgemein anwendbare Lösungsstrategien, die sogar spezielle Verfahren schlagen: Das Divide-and-Color-Verfahren läßt sich etwa anwenden auf eine Reihe von Problemen wie z.B. Longes Path oder Graph-Packing-Probleme wie Triangle Packing. Die allgemeine Technik des Expandierens von allen Knotenmengen mit einer gewissen Eigenschaft (Enumerate-and-Expand) verwendeten wir für schnellere Algorithmen für Connected Vertex Cover und Tree Cover, beides Varianten des wohlbekannten Vertex Cover-Problems.

Publications

• Parameterized power domination complexity. Technical Report AIB-2004-09, Dept. of Computer Science, RWTH Aachen University, December 2004
  J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
  
• A faster algorithm for the Steiner tree problem. Technical Report AIB-2005-04, Dept. of Computer Science, RWTH Aachen University, March 2005
  D. Mölle, S. Richter, and P. Rossmanith
  
• On the parameterized complexity of exact satisfiability problems. In: J. Jędrzejowicz and A. Szepietowski, editors. Proceedings of the 30th Conference on Mathematical Foundations of Computer Science (MFCS), number 3618 in Lecture Notes in Computer Science, pages 568-579. Springer, 2005
  J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
  
• A faster algorithm for the Steiner tree problem. In: Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STAGS), number 3884 in Lecture Notes in Computer Science, pages 561-570. Springer, 2006
  D. Mölle, S. Richter, and P. Rossmanith
  
• Divide-andcolor. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), number 4271 in Lecture Notes in Computer Science, pages 58-67. Springer, 2006
  J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
  
• Divide-andcolor. Technical Report AIB-2006-06, RWTH Aachen University, May 2006
  J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
  
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. In: Proceedings of the 1st International Computer Science Symposium in Russia (CSR), number 3967 in Lecture Notes in Computer Science, pages 270-280. Springer, 2006
  D. Mölle, S. Richter, and P. Rossmanith
  
• Enumerate and expand: New runtime bounds for vertex cover variants. In: Proceedings of the 12th Annual International Computing and Com,binatorics Conference (COCOON), number 4112 in Lecture Notes in Computer Science, pages 265-273. Springer, 2006
  D. Mölle, S. Richter, and P. Rossmanith
  
• Parameterized power domination complexity. Information Processing Letters, 98(4):145-149, 2006
  J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
  
• Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 41(3):493-500, 2007
  B. Fuchs, W. Kern, D. Mölle, S. Richter, P. Rossmanith, and X. Wang
  
• Exact Algorithms Based on Specific Complexity Measures for Hard Problems. PhD thesis, RWTH-Aachen, 2007
  D. Mölle
  
• A practical approach to Courcelle's Theorem. In: Proceedings of the 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (ME-MICS), pages 99-106. Z. Novotny, 2008
  J. Kneis and A. Langer
  
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory of Computing Systems, 43(2):234-253, 2008
  D. Mölle, S. Richter, and P. Rossmanith
  
• New fixed-parameter algorithms for the minimum quartet inconsistency problem. In: Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC), number 5018 in Lecture Notes in Computer Science, pages 66-77. Springer, 2008
  M.-S. Chang, C.-C. Lin, and P. Rossmanith
  
• Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM Journal on Computing, 38(6):2526-2547, 2009
  J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S. Sze, and F. Zhang