Executive Summary : | Parameterized Complexity is an approach that extends the notion of feasible computation for NP-complete problems. It focuses on polynomial-time algorithms that are considered feasible computation. For example, the VERTEX COVER problem is a well-known NP-hard problem where a graph has at most k vertices with at least one endpoint in S. A naive algorithm would require O(n^k)-time to solve, but a careful systematic algorithm can solve it in O(2^k poly(n))-time. An input instance to a parameterized problem is (x, k), which can be related to the input instance, such as solution size or the size of the input structure. If an algorithm with running time f(k)poly(x)-time is found for a parameterized problem L, it is said to be fixed-parameter tractable. Kernelization or parameterized preprocessing is an important step in designing parameterized algorithms. Enumerating all solutions of computational problems is a fundamental task in computer science. If a combinatorial problem is polynomial-time solvable but the number of solutions is exponential in the size of the input instance, it is expected that the algorithm will have FPT-delay. Golovach et al. have developed a refined notion of enumeration in kernelization, which aims to obtain a bounded output-instance and satisfy an additional property. Exploring parameterized enumeration problems with a special focus on polynomial-delay is an interesting line of research. |