Mehr als Kernelisierung – Mehr Allgemeinheit für effiziente Vorverarbeitung

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 einen 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.