# Incremental FPT Delay
## 2 Preliminaries
### Parameterized Enumeration  
Having introduced the basic principles in parameterized complexity theory and enumeration complexity theory, we introduce a combined version of these notions.  
**Definition 6** ([19]).: _A parameterized enumeration problem (PEP) over an alphabet \(\Sigma\) is a triple \(E=(Q,\kappa,\mathrm{Sol})\), where_  
* \(\kappa\colon\Sigma^{*}\to\mathbb{N}\) _is a parameterization (that is, a polynomial-time computable function), and_
* \((Q,\mathrm{Sol})\) _is an EP._  
The definitions of enumeration algorithms and delays are easily lifted to the setting of PEPs. Observe that the following defined classes are in complete analogy to the nonparameterized case from the previous section.  
**Definition 7** ([19]).: _Let \(E=(Q,\kappa,\mathrm{Sol})\) be a PEP and \(\mathcal{A}\) an enumeration algorithm for \(E\). Then the algorithm \(\mathcal{A}\) is_  
1. _an_ FPT_-enumeration algorithm if there exists a computable function_ \(t\colon\mathbb{N}\to\mathbb{N}\) _and a polynomial_ \(p\) _such that for every instance_ \(x\in\Sigma^{*}\)_,_ \(\mathcal{A}\) _outputs_ \(\mathrm{Sol}(x)\) _in time at most_ \(t(\kappa(x))\cdot p(|x|)\)_,_
2. \(a\) DelayFPT_-algorithm if there exists a computable function_ \(t\colon\mathbb{N}\to\mathbb{N}\) _and a polynomial_ \(p\) _such that for every_ \(x\in\Sigma^{*}\)_,_ \(\mathcal{A}\) _outputs_ \(\mathrm{Sol}(x)\) _with delay of at most_ \(t(\kappa(x))\cdot p(|x|)\)_,_
3. _an_ IncFPT_-algorithm if there exists a computable function_ \(t\colon\mathbb{N}\to\mathbb{N}\) _and a polynomial_ \(p\) _such that for every_ \(x\in\Sigma^{*}\)_,_ \(\mathcal{A}\) _outputs_ \(\mathrm{Sol}(x)\) _and its_ \(i\)_-th delay is at most_ \(t(\kappa(x))\cdot p(|x|,i)\)_, and_
4. _an_ OutputFPT_-algorithm if there exists a computable function_ \(t\colon\mathbb{N}\to\mathbb{N}\) _and a polynomial_ \(p\) _such that for every instance_ \(x\in\Sigma^{*}\)_,_ \(\mathcal{A}\) _outputs_ \(\mathrm{Sol}(x)\) _in time at most_ \(t(\kappa(x))\cdot p(|x|,|\mathrm{Sol}(x)|)\)_._  
Note that, as before, the notion of TotalFPT has been used for the class of FPT-enumerable problems [18]. We avoid this name as it causes confusion with respect to an enumeration class TotalP ([40], Section 3.1), which takes into account not only the size of the input but also the number of solutions. We call this class OutputP instead and, accordingly, it is the nonparameterized analogue of the above class OutputFPT. Now, we group these different kinds of algorithms in complexity classes.  
The class EnumFPT/DelayFPT/IncFPT/OutputFPT is the class of all PEPs that admit an FPT-enumeration/DelayFPT-/IncFPT-/OutputFPT-algorithm.  
The class DelayFPT captures a good notion of tractability for parameterized enumeration complexity. [PERSON] et al. [19] identified a multitude of problems that admit DelayFPT enumeration. Note that, due to [PERSON] and Grohe ([15], Proposition 1.34) the class \(\mathsf{FPT}\) can be characterized via runtimes of the form either \(f(\kappa(x))\cdot p(|x|)\) or \(f(\kappa(x))+p(|x|)\) (as \(a\cdot b\leq a^{2}+b^{2}\), for all \(a,b\in\mathbb{N}\)). Accordingly, this applies also to the introduced classes \(\mathsf{DelayFPT}\), \(\mathsf{IncFPT}\), and \(\mathsf{OutputFPT}\).