Effiziente Vorverarbeitungsalgorithmen, Kernels und Parametrisierte Komplexitätstheorie

• Antragsteller: Professor Dr. Peter Rossmanith
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 206471640

Kernelization ist ein Bereich der parametrisierten Komplexitätstheorie, der sich dem Studium von Preprocessing-Algorithmen widmet. Solche Algorithmen entfernen im Wesentlichen die einfachen Teile einer Probleminstanz und legen auf diese Weise den harten Kern, genannt kernel, frei. Dieser Forschungsbereich ist sowohl aus theoretischer als auch aus praktischer Sicht interessant, da er auf der einen Seite viele interessante mathematische Probleme birgt, auf der anderen Seite die erzielten Ergebnisse oft auch von großem praktischen Nutzen sind. Das Ziel dieses Projektes ist es, sowohl theoretische als auch praktische Aspekte von solchen Preprocessing-Algorithmen zu untersuchen. Auf der theoretischen Seite möchten wir unter anderem kernelization für alternative Parameter studieren, etwa für Parameter, die etwas über die Struktur der Eingabeinstanz aussagen. Weitere geplante Themen sind strong polynomial kernels, Turing kernels, und die Beziehung von kernelization und Approximierbarkeit. Auf der praktische Seite planen wir, Preprocessing-Algorithmen für konkrete Probleme mit dem Ziel einer praktischen Umsetzung zu entwerfen. Insbesondere möchten wir Möglichkeiten untersuchen, bekannte kernel für verschiedene Probleme auf planaren Graphen zu verbessern.

• DFG-Verfahren: Sachbeihilfen