Dr. Rolf Niedermeier

"Parametrisierte Komplexität in Theorie und Praxis"

Die Untersuchung parametrisierter Komplexität etabliert sich immer mehr als eine weitere Möglichkeit zur Behandlung NP-schwieriger Probleme.

Grundidee hierbei ist die Ermittlung von Problemparametern, auf die dann die bei solchen Problemen anscheinend unumgänglich auftretende kombinatorische Explosion beschränkt werden soll. Das wohl bekannteste Beispiel hierfür ist ein parametrisierter Algorithmus für das NP-vollständige Knotenüberdeckungsproblem (Vertex Cover) auf Graphen, welcher kurz besprochen werden wird.

Im Rahmen des Vortrags wird ein kurzer Überblick zu den Möglichkeiten und Grenzen von parametrisierten Algorithmen gegeben. Es werden erfolgreiche Anwendungen des Ansatzes auf kombinatorische Graphprobleme und Probleme aus der algorithmischen Biologie vorgestellt. Die Güte der vorgestellten Algorithmen wird durch Tests empirisch bestätigt. Schließlich werden kurz neue komplexitätstheoretische Ergebnisse diskutiert, welche Grenzen des parametrisierten Ansatzes aufzeigen.