# Incremental FPT Delay
## 2 Preliminaries
### Parameterized Complexity Theory  
We present a brief introduction into the field of parameterized complexity theory. For a deeper introduction, we kindly refer the reader to the textbooks of [PERSON] [15], [PERSON] [16], or Downey and Fellows [13].  
Let \(Q\subseteq\Sigma^{*}\) be a decision problem over some alphabet \(\Sigma\). Given an instance \(\langle x,k\rangle\in Q\times\mathbb{N}\), we call \(k\) the _parameter's value (of \(x\))_. Often, instead of using tuple notation for instances, one uses a polynomial time computable function \(\kappa\colon\Sigma^{*}\to\mathbb{N}\) (the _parameterization_) to address the parameter's value of an input \(x\). Then, we write \((Q,\kappa)\) denoting the _parameterized problem_ (PP).  
**Definition 1** (Fixed-parameter tractable): _Let \((Q,\kappa)\) be a parameterized problem over some alphabet \(\Sigma\). If there exists a deterministic algorithm \(A\) and a computable function \(f\colon\mathbb{N}\to\mathbb{N}\) such that for all \(x\in\Sigma^{*}\)_  
* \(A\) _accepts_ \(x\) _if and only if_ \(x\in Q\)_, and_
* \(A\) _has a runtime of_ \(f(\kappa(x))\cdot|x|^{O(1)}\)_,_  
_Then \(A\) is an fpt-algorithm for \((Q,\kappa)\) and \((Q,\kappa)\) is fixed-parameter tractable (or short, in the complexity class FPT)._  
[PERSON] and [PERSON] [15] provide a way to \"parameterize\" a classical and _robust_ complexity class. For our purposes, para-NP suffices, and accordingly, we do not present the general scheme.  
**Definition 2** (para-NP, ([15], Definition 2.10)): _Let \((Q,\kappa)\) with \(Q\subseteq\Sigma^{*}\) be a parameterized problem over some alphabet \(\Sigma\). We have \((Q,\kappa)\in\mathsf{para-NP}\) if there exists a computable function \(f\colon\mathbb{N}\to\mathbb{N}\) and a nondeterministic algorithm \(N\) such that for all \(x\in\Sigma^{*}\), \(N\) correctly decides whether \(x\in Q\) in at most \(f(\kappa(x))\cdot p(|x|)\) steps, where \(p\) is a polynomial._  
Furthermore, [PERSON] and [PERSON] characterize the class para-NP via all problems \"_that are in_ NP _after precomputation on the parameter\"._  
**Proposition 1** ([15], Proposition 2.12): _Let \((Q,\kappa)\) be a parameterized problem over some alphabet \(\Sigma\). We have \((Q,\kappa)\in\mathsf{para-NP}\) if and only if there exists a computable function \(\pi\colon\Sigma^{*}\to\Sigma^{*}\) and a problem \(Q^{\prime}\subseteq\Sigma^{*}\times\Sigma^{*}\) such that \(Q^{\prime}\in\mathsf{NP}\) and the following is true: For all instances \(x\in\Sigma^{*}\), we have that \(x\in Q\) if and only if \((x,\pi(\kappa(x)))\in Q^{\prime}\)._  
According to the well-known characterization of the complexity class NP via a verifier language, one can easily deduce the following corollary, which is later utilized to explain Definition 11.  
**Corollary 1**: _Let \((Q,\kappa)\) be a parameterized problem over some alphabet \(\Sigma\) and \(p\) some polynomial. We have \((Q,\kappa)\in\mathsf{para-NP}\) if there exists a computable function \(\pi\colon\Sigma^{*}\to\Sigma^{*}\) and a problem \(Q^{\prime}\subseteq\Sigma^{*}\times\Sigma^{*}\times\Sigma^{*}\) such that \(Q^{\prime}\in\mathsf{P}\) and the following is true: For all instances \(x\in\Sigma^{*}\), we have that \(x\in Q\) if and only if there exists a \(y\) such that \(|y|\leq p(|x|)\) and \((x,\pi(\kappa(x)),y)\in Q^{\prime}\)._