Average-Case Analysis of Parameterized Problems and Algorithms

• Applicants: Professor Tobias Friedrich, Ph.D.; Professor Dr. Jiong Guo
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 213251566

Viele praktisch auftretende Probleme sind NP-schwer. Um diese zu lösen, haben sich zwei Ansätze als erfolgreich herausgestellt. Das sind einerseits Festparameteralgorithmen, bei denen angenommen wird, dass ein bestimmter Parameter der Probleminstanzen klein ist, und andererseits Average-Case Komplexität, bei der angenommen wird, dass die Eingaben einer gewissen statistischen Verteilung entstammen. Obwohl Zufall beim Design parametrisierter Algorithmen verwendet wird, ist das Average-Case Verhalten von parametrisierten Problemen und Algorithmen bisher kaum untersucht. Als erstes soll in diesem Projekt das Average-Case Verhalten von bekannten parametrisierten Algorithmen untersucht werden. Dies ist motiviert durch eine Vielzahl von experimentellen Untersuchungen parametrisierter Algorithmen, welche für verschiedene Probleme beobachtet haben, dass die Laufzeiten auf realen und zufälligen Instanzen wesentlich geringer sind als die bewiesenen Worst-Case Schranken. Weiterhin möchten wir klassische parametrisierte Probleme wie Clique betrachten, welche im Worst-Case nicht parametrisiert lösbar sind. Das Ziel hierbei ist zu zeigen, dass einige dieser Worst-Case schweren Probleme im Average-Case effizient lösbar sind.

• DFG Programme: Research Grants