Nutzung neuer Arten von Struktur in parametrisierten Algorithmen

Viele wichtige algorithmische Probleme sind im allgemeinen nicht effizient lösbar, aber oft ist es möglich, gewisse strukturelle Eigenschaften von Problemeingaben auszunutzen um dennoch eine effiziente Lösung zu erreichen. Bisherige Forschung hat verschieden strukturellen Eigenschaften identifiziert, welche die Lösung des Problems in Polynomialzeit ermöglichen. Eine zentrale Frage dieses Forschungsprojektes ist es, wie diese effizienten Lösungsmethoden auch für solche Problemeingaben nutzbar gemacht werden können, die diese strukturellen Eigenschaften nicht zur Gänze erfüllen. Im Speziellen soll die Lösbarkeit von Problemeingaben untersucht werden, bei denen gewisse strukturelle Eigenschaften durch eine kleine Anzahl von elementaren Änderungen erreicht werden können. Die Anzahl dieser Änderungen dient als Parameter für parametrisierte Algorithmen. Das Gesamtziel ist es, eine rigorose Methodik zu entwickeln, die für viele wichtige algorithmische Problem anwendbar ist, und die es ermöglicht, strukturelle Eigenschaften von Problemeingaben auszunutzen, die für bekannte Methoden nicht nutzbar sind. Neben effizienten Algorithmen sollen auch euch neue Methoden für untere Schranken für Laufzeitanalysen entwickelt werden.

Viele wichtige algorithmische Probleme sind im allgemeinen nicht effizient lösbar, aber oft ist es möglich, gewisse strukturelle Eigenschaften von Problemeingaben auszunutzen, um dennoch eine effiziente Lösung zu erreichen. Die bisherige Forschung hat verschiedene strukturelle Eigenschaften identifiziert, welche die Lösung von Problemen in Polynomialzeit ermöglichen. Eine zentrale Frage dieses Forschungsprojektes war es, wie diese effizienten Lösungsmethoden auch für solche Problemeingaben nutzbar gemacht werden können, die diese strukturellen Eigenschaften nicht zur Gänze erfüllen. Im Speziellen haben wir die Lösbarkeit von Problemeingaben untersucht, bei denen die gewünschten strukturellen Eigenschaften durch eine kleine Anzahl von elementaren Änderungen erreicht werden können. Die Anzahl dieser Änderungen dient als grundlegender Parameter für parametrisierte Algorithmen. Es gelang uns Algorithmen zu entwickeln, die auch dann anwendbar sind, wenn die Anzahl dieser Änderungen zwar groß ist, jedoch die Interaktion zwischen den einzelnen Änderungen gewisse strukturelle Eigenschaften aufweist. Dies haben wir unter anderem für die effiziente Lösung des Constraint Satisfaction Problems (CSP) eingesetzt. Wir haben auch intensiv an effizienten Methoden zur Lösung des Integer Linear Programming (ILP) Problems gearbeitet. Wir konnten genau beschreiben, wie sich die Komplexität von ILP verhält, wenn die Interaktion zwischen Variablen von beschränkter Baumweite ist.