Parametrisierte Komplexität und exakte Algorithmen

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1999 bis 2007
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5212814

Das Studium der parametrisierten Komplexität von NP-harten Problemen gilt als einer der neuesten Vorschläge zur Handhabung von kombinatorisch schwierigen Problemen. Die Grundidee besteht in der Isolierung eines oder mehrerer Parameter als Teil des Problems, auf welchen die anscheinend problem-inhärente "kombinatorische Explosion" beschränkt werden kann. Für kleine bis mittlere Parametergrößen sind damit effiziente exakte Algorithmen für ansonsten harte Probleme möglich. Als Formalisierung zur Beschreibung parametrisierter Probleme, welche effiziente parametrisierte Algorithmen besitzen, dient die Komplexitätsklasse FPT. Aber schon Downey und Fellows, die Begründer der parametrisierten Komplexität, schreiben am Ende der Einleitung zu ihrer neuen Monographie "Parameterized Complexity": "The positive toolkit for designing FPT algorithms contains several key methods that are very deep and general - but for which practicality is still not clearly established. Much remains to be explored." Anliegen des Projektes ist es, Stärken und Schwächen der parametrisierten Komplexität zu bestimmen und die Frage nach der praktischen Relevanz des Konzeptes ihrer Klärung näher zu bringen. Für konkrete Einzelprobleme (insbesondere Graphenprobleme), die praktisch motiviert sind, sollen darüberhinaus Implementierungen effizienter parametrisierter Algorithmen verwirklicht und auf ihre Praxistauglichkeit geprüft werden.

• DFG-Verfahren: Sachbeihilfen
• Beteiligte Person: Professor Dr. Klaus-Jörn Lange