# Parameterised Enumeration for Modification Problems +
## 4 Generalisation to Modification Problems
On that account, let \(\mathcal{P}\) be a property, \(\Pi=(Q,\kappa)\) be a parametrised problem with \(Q\subseteq\Sigma^{*}\) and \(\Omega\) be a set of operations. \begin{tabular}{l l} \hline \hline
**Problem:** & \(\Pi_{\mathcal{P}}\)--parameterised modification problem \(\Pi\) w.r.t. a property \(\mathcal{P}\) over \(\Sigma\) \\ \hline
**Input:** & \(x\in\Sigma^{*}\), \(k\in\mathbb{N}\), \(\Omega/x\) set of operations. \\
**Parameter:** & The integer \(k\). \\
**Question:** & Is there a solution \(S\subseteq\Omega/x\) and \(|S|\leq k\)? \\ \hline \hline
**Problem:** & Enum-Min-\(\Pi_{\mathcal{P}}\)--parameterised minimum enumeration modification problem \\  & w.r.t. a property \(\mathcal{P}\) over \(\Sigma\) \\ \hline
**Input:** & \(x\in\Sigma^{*}\), \(k\in\mathbb{N}\), \(\Omega/x\) set of operations. \\
**Parameter:** & The integer \(k\). \\
**Output:** & All minimal (w.r.t. some order) solutions \(S\subseteq\Omega/x\) with \(|S|\leq k\). \\ \hline \hline \end{tabular}   
The enumeration modification problem where we want to output all possible sets of transformations on a given instance \(x\) (and not only the minimum ones) then is Enum-\(\Pi_{\mathcal{P}}\). In the following, we show how the notion of neighbourhood functions can be generalised as well. This will in turn yield generalisations of the results for graph modification problems afterwards. **Definition 12**. : _Let \(\Sigma\) be an alphabet, \(\mathcal{P}\subseteq\Sigma^{*}\) be a property and \(\Pi_{\mathcal{P}}\) be a parameterised modification problem over \(\Sigma\). A neighbourhood function for \(\Pi_{\mathcal{P}}\) is a (partial) function \(\mathcal{N}_{\Pi_{\mathcal{P}}}\colon\Sigma^{*}\times\left(\mathcal{S}_{\Pi _{\mathcal{P}}}\cup\{\mathbb{O}\}\right)\to 2^{\Pi_{\mathcal{P}}}\) such that the following holds:_  
1. _For all_ \(x\in\Sigma^{*}\) _and_ \(S\in\operatorname{Sol}_{\Pi_{\mathcal{P}}}(x)\cup\{\mathbb{O}\}\)_,_ \(\mathcal{N}_{\Pi_{\mathcal{P}}}(x,S)\) _is defined._
2. _For all_ \(x\in\Sigma^{*}\)_,_ \(\mathcal{N}_{\Pi_{\mathcal{P}}}(x,\mathbb{O})=\emptyset\) _if_ \(\operatorname{Sol}_{\Pi_{\mathcal{P}}}(x)=\emptyset\)_, and_ \(\mathcal{N}_{\Pi_{\mathcal{P}}}(x,\mathbb{O})\) _is an arbitrary set of solutions otherwise._
3. _For all_ \(x\in\Sigma^{*}\) _and_ \(S\in\operatorname{Sol}_{\Pi_{\mathcal{P}}}(x)\)_, if_ \(S^{\prime}\in\mathcal{N}_{\Pi_{\mathcal{P}}}(x,S)\) _then_ \(|S|<|S^{\prime}|\)_._
4. _For all_ \(x\in\Sigma^{*}\) _and all_ \(S\in\operatorname{Sol}_{\Pi_{\mathcal{P}}}(x)\)_, there exists_ \(p>0\) _and_ \(S_{1},\ldots,S_{p}\in\operatorname{Sol}_{\Pi_{\mathcal{P}}}(x)\) _such that (i)_ \(S_{1}\in\mathcal{N}_{\Pi_{\mathcal{P}}}(x,\mathbb{O})\)_, (ii)_ \(S_{i+1}\in\mathcal{N}_{\Pi_{\mathcal{P}}}(x,S_{i})\) _for_ \(1\leq i<p\) _and (iii)_ \(S_{p}=S\)_._  
_Furthermore, we say that \(\mathcal{N}_{\Pi_{\mathcal{P}}}\) is FPT computable when \(\mathcal{N}_{\Pi_{\mathcal{P}}}(x,S)\) is computable in time \(f(k)\cdot\mathit{poly}(|x|)\) for any \(x\in\Sigma^{*}\) and \(S\in\operatorname{Sol}_{\Pi_{\mathcal{P}}}(x)\)._  
As already announced before, we are able to state generalised versions of Theorems 1 and 2 which can be proven in a similar way. However, one has to replace the graph modification problems by general modification problems. **Corollary 6**: _Let \(\mathcal{P}\) be a property, \(\Pi\subseteq\Sigma^{*}\times\mathbb{N}\) be a parameterised modification problem and \(\Omega\) be a set of operations such that \(\Omega/x\) is finite for all \(x\in\Sigma^{*}\). If \(\Pi_{\mathcal{P}}\) admits a neighbourhood function that is FPT computable then \(\textsc{Enum-}\Pi_{\mathcal{P}}\in\textsc{DelayFPT}\) using_  
* _polynomial space for lexicographic order and_
* _exponential space for size order._  
**Corollary 7**: _Let \(\mathcal{P}\) be a property, \(\Pi\subseteq\Sigma^{*}\times\mathbb{N}\) be a parameterised modification problem and \(\Omega\) be a set of operations such that \(\Omega/x\) is finite for all \(x\in\Sigma^{*}\).