# Incremental FPT Delay
## 3 Interleaving Hierarchies of Parameterized Incremental Delay  
The previous observations raise the question of how \(\mathsf{DelayFPT}\) relates to \(\mathsf{IncFPT}\). In the classical enumeration world, this question has been partially answered by [PERSON] and [PERSON] ([12], Proposition 16) for a weaker capped version of incremental polynomial time: \(\mathsf{DelayP}\subsetneq\mathsf{CapIncP}\) is true for the restriction to solution sets that do not necessarily obey the last two items of Definition 3 (they call this class \(\mathsf{Enum}\cdot\mathsf{F}\)). Only for linear total time and polynomial space under this setting is the relation not completely understood, that is, the question how \(\mathsf{DelayP}\) with polynomial space relates to \(\mathsf{CapIncP}_{1}\) with polynomial space ([12], Open Problem 1, p. 10). In the course of this chapter, it is shown that the relationship between the classical and the parameterized world is very close. [PERSON] and [PERSON] approach the separation mentioned above through the classes \(\mathsf{CapIncP}_{a}\) and prove a strict hierarchy of these classes. We lift this to the parameterized setting. **Definition 8** (Sliced Versions of Incremental FPT Delay, extending Definition 7). : _Let \(E=(Q,\kappa,\mathrm{Sol})\) be a PEP and \(\mathcal{A}\) an enumeration algorithm for \(E\). Then, algorithm \(\mathcal{A}\) is_  
1. _[label=\(\ref{eq:Capelli}\)]_
2. \(a\) \(\mathsf{CapIncFPT}_{a}\)_-algorithm (for_ \(a\in\mathbb{N}\)_) 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_ \(i\) _elements of_ \(\mathrm{Sol}(x)\) _in time_ \(t(\kappa(x))\cdot i^{a}\cdot p(|x|)\) _(for every_ \(0\leq i\leq|\mathrm{Sol}(x)|\)_)._
3. _an_ \(\mathsf{IncFPT}_{a}\)_-algorithm (for_ \(a\in\mathbb{N}\)_) 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 i^{a}\cdot p(|x|)\)_._  
_Similarly, we define a hierarchy of classes \(\mathsf{CapIncFPT}_{a}\) for every \(a\in\mathbb{N}\) which consist of problems that admit an \(\mathsf{CapIncFPT}_{a}\)-algorithm. Moreover, \(\mathsf{CapIncFPT}:=\bigcup_{a\in\mathbb{N}}\mathsf{CapIncFPT}_{a}\)._  
Clearly, \(\bigcup_{a\in\mathbb{N}}\mathsf{IncFPT}_{a}=\mathsf{IncFPT}\) and \(\mathsf{IncFPT}_{0}=\mathsf{DelayFPT}\) by Definition 7 as the \(i\)-th delay then merely is \(t(\kappa(x))\cdot p(|x|)\), as \(i^{0}=1\). Usually, one utilizes a priority queue to store the already printed solutions as it allows for efficiently detecting duplicates. Nevertheless, it is unclear how to detect duplicates of solutions without storing them in the queue. Currently, it seems that the price of a \"regular\" (that is, polynomial) delay then is paid by the need for exponential space. Agreeing with [PERSON] and [PERSON] ([12], Section 3), it seems very reasonable to see the difference of \(\mathsf{IncFPT}_{1}\) and \(\mathsf{DelayFPT}\) anchored in the presence of an exponential sized priority queue. However, relaxing this statement shows that the equivalence of incremental \(\mathsf{FPT}\) delay and capped incremental \(\mathsf{FPT}\)-time is also true in the parameterized world. Similarly, as in the classical setting ([12], Proposition 12), the benefit of a structured delay can be reached with the exponential space of a priority queue. To lift the argumentation in the proof to the parameterized setting, one needs to keep track of the factors of the kind \(t(\kappa(x))\) in the process. The remainder of the argumentation is the same. **Theorem 1**. : _For every \(a\geq 0\), \(\mathsf{CapIncFPT}_{a+1}=\mathsf{IncFPT}_{a}\)._  
**Proof. ** \"\(\supseteq\)\": Let \(E=(Q,\kappa,\text{Sol})\) be a PEP in \(\text{IncFPT}_{a}\) via an algorithm \(\mathcal{A}\).