# Parameterised Enumeration for Modification Problems +
## 2 Preliminaries  
We start by defining parameterised enumeration problems with a specific ordering and their corresponding enumeration algorithms. Most definitions in this section transfer those of [PERSON] et al. and [PERSON] (2015); [PERSON] et al. (2016) from the context of enumeration and those of [PERSON] et al. (2016) from the context of parameterised enumeration to the context of parameterised ordered enumeration. The studied orderings of enumeration problems in this paper are quasi-orders which will be defined in the following. **Definition 1** (Quasi-Order). : _Let \(R\) be a set and \(\preceq\) a binary relation on \(R\). Then \(\preceq\) is a preorder (or quasi-order) if we have for all elements \(a,b,c\in R\):_  
* \(a\preceq a\) _and_
* _if_ \(a\preceq b\) _and_ \(b\preceq c\) _then_ \(a\preceq c\)_._  
We will write \(z\
ot\preceq y\) whenever \(z\preceq y\) is not true. Now, we proceed by introducing parameterised enumeration problems with ordering. Intuitively, the corresponding enumeration algorithm for such problems has to obey the given ordering, that is, it has to produce solutions without violating that ordering. **Definition 2**. : _A parameterised enumeration problem with ordering is a quadruple \(E=(I,\kappa,\operatorname{Sol},\preceq)\) such that the following holds:_  
* \(I\) _is the set of instances._
* \(\kappa\colon I\to\mathbb{N}\) _is the parameterisation function;_ \(\kappa\) _is required to be polynomial time computable._
* \(\operatorname{Sol}\) _is a function such that for all_ \(x\in I\)_,_ \(\operatorname{Sol}(x)\) _is a finite set, the set of solutions of_ \(x\)_. Further we write_ \(\mathcal{S}=\bigcup_{x\in I}\operatorname{Sol}(x)\)_._
* \(\preceq\) _is a quasi-order on_ \(\mathcal{S}\)_._  
Notice that this order on all solutions is only a short way of simultaneously giving an order for each instance. Furthermore, we will write an index \(E\) letter, e.g., \(I_{E}\), \(\kappa_{E}\), to denote that we are talking about an instance set, parameterisation function, etc., of a given enumeration problem \(E\). In the next step, we fix the notion of enumeration algorithms in our setting. **Definition 3** (Enumeration Algorithm). : _Let \(E=(I,\kappa,\operatorname{Sol},\preceq)\) be a parameterised enumeration problem with ordering. Then an algorithm \(\mathcal{A}\) is an enumeration algorithm for \(E\) if the following holds:_  
* _For every_ \(x\in I\)_,_ \(\mathcal{A}(x)\) _terminates after a finite number of steps._
* _For every_ \(x\in I\)_,_ \(\mathcal{A}(x)\) _outputs exactly the elements of_ \(\operatorname{Sol}(x)\) _without duplicates._
* _For every_ \(x\in I\) _and_ \(y,z\in\operatorname{Sol}(x)\)_, if_ \(y\preceq z\) _and_ \(z\
ot\preceq y\) _then_ \(\mathcal{A}(x)\) _outputs solution_ \(y\) _before solution_ \(z\)_._  
Before we define complexity classes for parameterised enumeration, we need the notion of delay for enumeration algorithms. **Definition 4** (Delay). : _Let \(E=(I,\kappa,\operatorname{Sol},\preceq)\) be a parameterised enumeration problem with ordering and \(\mathcal{A}\) be an enumeration algorithm for \(E\). Let \(x\in I\) be an instance. The \(i\)th delay of \(\mathcal{A}\) is the elapsed runtime with respect to \(|x|\) of \(\mathcal{A}\) between outputting the \(i\)th and \((i+1)\)th solution in \(\operatorname{Sol}(x)\). The \(0\)th delay is the precomputation time which is the elapsed runtime with respect to \(|x|\) of \(\mathcal{A}\) from the start of the computation to the first output statement. Analogously, the \(n\)th delay, for \(n=|\operatorname{Sol}(x)|\), is the postcomputation time, which is the elapsed runtime with respect to \(|x|\) of \(\mathcal{A}\) after the last output statement until \(\mathcal{A}\) terminates. Then, the delay of \(\mathcal{A}\) is the maximum over all \(0\leq i\leq n\) of the \(i\)th delay of \(\mathcal{A}\)._  
Now we are able to define two different complexity classes for parameterised enumeration following the notion of [PERSON] et al. (2016). **Definition 5**.