Mehr als Kernelisierung – Mehr Allgemeinheit für effiziente Vorverarbeitung

• Antragsteller: Professor Dr. Stefan Kratsch
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 526215872

Effiziente Vorverarbeitung ist ein vielseitiger und allgemeiner Ansatz um Berechnungen zu beschleunigen. Die gründliche Untersuchung effizienter Vorverarbeitung für NP-schwere Probleme wurde durch den Begriff der Kernelisierung (engl. kernelization) aus der parametrisierten Komplexität möglich gemacht (engl. parameterized complexity). Eine (polynomielle) Kernelisierung (engl. (polynomial) kernelization) ist ein effizienter Algorithmus, der bei Eingabe einer Inputinstanz eine equivalente Outputinstanz zurückgibt. Die Größe dieser Outputinstanz ist dabei beschränkt durch eine (polynomielle) Funktion abhängig von einem festgelegten Parameter der Eingabe, z.B. der Lösungsgröße. Mittlerweile ist es gut verstanden, ob Probleme bezüglich bestimmter Parameter eine polynomielle Kernelisierung erlauben (modulo üblicher Komplexitätsannahmen). Leider ist ein Ergebnis dabei auch, dass viele Probleme keine polynomielle Kernelisierung erlauben. Ebenso sind positive Ergebnisse überwiegend auf Parameter beschränkt, die die Ähnlichkeit der Eingabe zu einem bestimmten effizient lösbaren Spezialfall für das Problem ausdrücken. Auch unter solchen Parametern gibt es noch viele einfache Fälle, die nachweislich keine polynomielle Kernelisierung erlauben. In diesem Projekt sollen verschiedene Relaxierungen des Begriffs der Kernelisierung genutzt werden, um diese Beschränkung zu umgehen, darunter sowohl bekannte als auch neue. Dabei sind sowohl approximative Kernelisierung als auch Turingkernelisierung sowie deren Kombination. Letztere wurde kürzlich genutzt um die ersten positiven Resultate für schwere Probleme unter dem Parameter der Baumweite (engl. treewidth) zu erzielen. Ebenso sollen lokale Formen von Kernelisierung untersucht werden, so dass keine so restriktiven Anforderungen für die Struktur der Eingabe gemacht werden müssen. Stattdessen soll es ausreichen, wenn ein Teil der Eingabe hinreichend strukturiert ist und sich dessen Interaktion mit dem Rest der Eingabe hinreichend kontrollieren lässt. Desweiteren wollen wir strukturelle Vorverarbeitung untersuchen, bei der andere Ziele als die Beschränkung der Größe der Ausgabeinstanz angestrebt werden. Stattdessen kann die Beschränkung anderer algorithmisch nützlicher Parameter ebenso vorteilhaft für die nachfolgende Berechnung sein, ganz im Sinne effizienter Vorverarbeitung. Insgesamt ist es das Ziel, aussagekräftige, positive Resultate für die effiziente Vorverarbeitung für schwere Probleme zu erzielen, und dabei deutlich weniger restriktive Bedingungen zu benötigen, als dies bisher möglich ist.

• DFG-Verfahren: Sachbeihilfen