# Incremental FPT Delay
## 2 Preliminaries
### Enumeration  
As already motivated in the beginning of this section, measuring the runtime of enumeration algorithms is usually abandoned beyond the study of OutputP. As a result, one inspects the uniformity of the flow of output solutions of these algorithms rather than their total running time. In view of this, one measures the delay between two consecutive outputs. [PERSON] et al. [1] laid the cornerstone of this intuition in a seminal paper and introduced the necessary tools and complexity notions. [PERSON], [PERSON] [PERSON] [3; 40] presented recent notions in this framework, which we aim to follow. In this paper, we only consider enumeration problems which are \"good\" in the sense of polynomially bounded solution lengths and polynomially verifiable solutions ([PERSON] and [PERSON] [12] call the corresponding class EnumP). A good textbook that introduces into the field of exact exponential algorithms is by [PERSON] and [PERSON] [41]. **Definition 3** (NP Enumeration Problem). : _An NP enumeration problem (EP) over an alphabet \(\Sigma\) is a tuple \(E=(Q,\mathrm{Sol})\), where_  
1. \(Q\subseteq\Sigma^{*}\) _is the set of instances (recognizable in polynomial time),_
2. \(\mathrm{Sol}\colon\Sigma^{*}\to\mathcal{P}(\Sigma^{*})\) _is a computable function such that for all_ \(x\in\Sigma^{*}\)_,_ \(\mathrm{Sol}(x)\) _is a finite set and_ \(\mathrm{Sol}(x)\
eq\emptyset\) _if and only if_ \(x\in Q\)_,_
3. \(\{(x,y)\mid y\in\mathrm{Sol}(x)\}\in\mathsf{P}\)_, and_
4. _there exists a polynomial_ \(p\) _such that for all_ \(x\in Q\) _and_ \(y\in\mathrm{Sol}(x)\) _we have_ \(|y|\leq p(|x|)\)_._  
Furthermore, we use the shorthand \(\mathcal{S}=\bigcup_{x\in Q}\mathrm{Sol}(x)\) to refer to the set of solutions for every possible instance. If \(E=(Q,\mathrm{Sol})\) is an EP over the alphabet \(\Sigma\), then we call strings \(x\in\Sigma^{*}\)_instances of \(E\)_, and \(\mathrm{Sol}(x)\) the _set of solutions of \(x\)_. An _enumeration algorithm_ (EA) \(\mathcal{A}\) for the EP \(E=(Q,\mathrm{Sol})\) is a deterministic algorithm which, on the input \(x\) of \(E\), outputs exactly the elements of \(\mathrm{Sol}(x)\) without duplicates, and which terminates after a finite number of steps on every input. The following definition fixes the ideas of measuring the 'flow of output solutions'. **Definition 4** (Delay). : _Let \(E=(Q,\mathrm{Sol})\) be an enumeration problem and \(\mathcal{A}\) be an enumeration algorithm for \(E\). For \(x\in Q\), we define the \(i\)-th delay of \(\mathcal{A}\) as the time between outputting the \(i\)-th and \((i+1)\)-st solution in \(\mathrm{Sol}(x)\). Furthermore, we set the \(0\)-th delay to be the precomputation phase, which is the time from the start of the computation to the first output statement. Analogously, the \(n\)-th delay, for \(n=|\mathrm{Sol}(x)|\), is the postcomputation phase, which is the time needed after the last output statement until \(\mathcal{A}\) terminates. If \(t\colon\mathbb{N}\to\mathbb{N}\), then, generally, \(\mathcal{A}\) is said to output \(\mathrm{Sol}(x)\) with delay \(O(t(|x|))\) if for all \(x\in Q\) and all \(i\in\mathbb{N}\) the \(i\)-th delay is in \(O(t(|x|))\)._  
Subsequently, we use the notion of delay to state the central enumeration complexity classes. **Definition 5**. : _Let \(E=(Q,\mathrm{Sol})\) be an enumeration problem and \(\mathcal{A}\) be an enumeration algorithm for \(E\). Then, \(\mathcal{A}\) is_  
1. \(a\) \(\mathsf{P}\)-enum_-algorithm if and only if there exists a polynomial_ \(p\) _such that for all_ \(x\in Q\)_, algorithm_ \(\mathcal{A}\) _outputs_ \(\mathrm{Sol}(x)\) _in time_ \(O(p(|x|))\)_._
2. \(a\) \(\mathsf{DelayP}\)_-algorithm if and only if there exists a polynomial_ \(p\) _such that for all_ \(x\in Q\)_, algorithm_ \(\mathcal{A}\) _outputs_ \(\mathrm{Sol}(x)\) _with delay_ \(O(p(|x|))\)_._
3.