Turning FPT decision methods into enumeration algorithms with FPT-delay

Abstract

Parametrisierte Algorithmen sind ein gut erforschtes Gebiet der Algorithmik und Komplexitätstheorie, das verwendet wird um Instanzen schwieriger Probleme zu identifizieren, die effizient lösbar sind. Allerdings wurden diese hauptsächlich im Kontext von Entscheidungs- und Optimierungsproblemen untersucht. In der Praxis wird jedoch oft die Ausgabe von mehreren oder sogar allen Lösungen, die gewisse Eigenschaften erfüllen, benötigt.Die Analyse von Aufzählungsproblemen hat zu einigen Methoden geführt, die oft verwendet werden können um alle Lösungen eines gegebenen Problems zu finden. Solche Algorithmen wurden vorwiegend entwickelt um polynomielle Zeit oder polynomielle Verzögerung zu erreichen.Trotz der Erfolge in beiden dieser Bereiche hat deren Kombination bisher kaum Aufmerksamkeit erlangt. Daher ist das Ziel dieser Arbeit Fortschritte im Gebiet der parametrisierten Aufzählungsalgorithmen zu machen. Spezifisch ist es das Ziel Aufzählungsalgorithmen mit FPT ('fixed-parameter-tractable') Verzögerung für eine Vielfalt an schwierigen Aufzählungsproblemen zu entwickeln.Zu diesem Zweck präsentieren wir zuerst den theoretischen Hintergrund von parametrisierter Komplexitätstheorie, Aufzählungsproblemen und deren Kombination. Dann untersuchen wir sowohl wie Methoden für Aufzählungsalgorithmen auf parametrisierte Probleme angewendet werden können als auch die Umwandlung von Verfahren für parametrisierte Algorithmen auf Aufzählungsalgorithmen. Damit lösen wir das entsprechende Aufzählungsproblem von einigen parametrisierten Entscheidungsproblemen.

Parameterized algorithms are a well-studied subject in algorithmics and complexity theory used to identify tractable fragments of hard problems. Yet they have been primarily been examined in the context of decision and optimization problems. However, in many practical contexts the output of multiple or even all solutions fitting certain restrictions is required.Research on enumeration problems has come up with several methods that can typically be used to design efficient algorithms for finding all solutions to a given problem. Such algorithms have been mainly investigated with the goal of achieving polynomial time or polynomial delay complexity.Despite the successes in both fields, their combination has received almost no attention so far. Therefore, the goal of this thesis is to advance the study of parameterized enumeration algorithms. More concretely, we aim at developing enumeration algorithms with fixed-parameter tractable delay for a variety of hard enumeration problems. To this end we first present a theoretical grounding of parameterized complexity, enumeration complexity and their combination. Then we explore how and where methods for finding enumeration algorithms can be applied to parameterized problems, as well as transforming methods used for parameterized algorithms to methods for enumeration. We use these to solve the associated enumeration problems for several parameterized decision problems.