From FPT Decision to FPT Enumeration

Abstract

Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems – with a focus on decision and optimization problems. Their aim is to confine the exponential explosion to some parameter, while the time complexity only depends polynomially on the instance size. In contrast, intractable enumeration problems have received comparatively little attention so far. The goal of this work is to study how FPT decision algorithms could be turned into FPT enumeration algorithms. We thus inspect several fundamental approaches for designing FPT decision or optimization algorithms and we present ideas how they can be extended to FPT enumeration algorithms.