From FPT Decision to FPT Enumeration
By: Nadia Creignou , Timo Camillo Merkl , Reinhard Pichler and more
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.
Similar Papers
FPT Parameterisations of Fractional and Generalised Hypertree Width
Data Structures and Algorithms
Helps computers solve harder problems faster.
Space Efficient Algorithms for Parameterised Problems
Data Structures and Algorithms
Solves big computer puzzles with less memory.
A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
Data Structures and Algorithms
Finds small groups of important connections faster.