# Parameterised Enumeration for Modification Problems +
## 3 Enumeration of Graph Modification Problems with Ordering
### Size Ordering
Consequently, each \(S_{i}\) is inserted in \(Q\) and then output during the run. In particular, this is true for \(S=S_{p}\). Finally, we claim that Algorithm 2 (see Figure 1 for a graphical representation) runs in DelayFPT time. Indeed, the delay between the output of two consecutive solutions is bounded by the time required to compute a neighbourhood of the form \(\mathcal{N}_{\mathcal{M}}((G,k,O),\mathbb{O})\) or \(\mathcal{N}_{\mathcal{M}}((G,k,O),S)\) and to insert all its elements in the priority queue. This is in FPT due to the assumption on \(\mathcal{N}_{\mathcal{M}}\) being FPT computable and as there is only a single extraction and many FPT insertion operations in the queue. ```
Input :\((G,k,O):G\) is an undirected graph, \(k\in\mathbb{N}\), and \(O\) is a set of operations. 1 compute \(\mathcal{N}_{\mathcal{M}}((G,k,O),\mathbb{O})\);
2 insert all elements of \(\mathcal{N}_{\mathcal{M}}((G,k,O),\mathbb{O})\) into priority queue \(Q\) (ordered by size);
3 while\(Q\) is not emptydo
4 extract the minimum solution \(S\) of \(Q\) and output it;
5 insert all elements of \(\mathcal{N}_{\mathcal{M}}((G,k,O),S)\) into \(Q\);
```  
**Algorithm 2**DelayFPT algorithm for Enum-\(\mathcal{M}\)  
A natural way to provide a neighbourhood function for a graph modification problem \(\mathcal{M}\) is to consider the inclusion minimal solutions of \(\mathcal{M}\). Let us denote by Min-\(\mathcal{M}\) the problem of enumerating all inclusion minimal solutions of \(\mathcal{M}\). Theorem 2.: _Let \(\mathcal{M}\) be a graph modification problem. If Min-\(\mathcal{M}\) is FPT enumerable then \(\textsc{Enum-}\mathcal{M}^{\textsc{SIZE}}\in\textsc{DelayFPT}\)._  
Proof. : Let \(\mathcal{A}\) be an FPT algorithm for Min-\(\mathcal{M}\). Because of Theorem 1, it is sufficient to build an FPT-neighbourhood function for \(\mathcal{M}\). For an instance \((G,k,O)\) of \(\mathcal{M}\) and for \(S\in\textsc{Sol}_{\mathcal{M}}(G,k,O)\cup\{\mathbb{O}\}\), we define \(\mathcal{N}_{\mathcal{M}}((G,k,O),S)\) as the result of Algorithm 3. ```
Input :\((G,k,O),S\): \(G\) is an undirected graph, \(k\in\mathbb{N}\), \(O\) and \(S\) are sets of operations. if\(S=\mathbb{O}\)thenreturn\(\mathcal{A}(G,k,O)\); res := \(\mathbb{O}\); for all\(t\in O\)do
1 for all\(S^{\prime}\in\mathcal{A}((S\cup\{t\})(G),k-|S|-1,O\setminus\{t\})\)do
2 if\(S\cup S^{\prime}\cup\{t\}\) is consistentthenres := res \(\cup\{S\cup S^{\prime}\cup\{t\}\}\) ;
3
4 return res;
```  
**Algorithm 3**Procedure for computing \(\mathcal{N}_{\mathcal{M}}((G,k,O),S)\)  
Accordingly, the function \(\mathcal{N}_{\mathcal{M}}\) clearly fulfils Conditions 2 and 3 of Definition 9. We prove by induction that it also satisfies Condition 4 (that is, each solution \(T\) of size \(k\) comes with a sequence \(T_{1},\ldots,T_{p}=T\) such that \(T_{1}\in\mathcal{N}_{\mathcal{M}}((G,k,O),\mathbb{O})\) and \(T_{i+1}\in\mathcal{N}_{\mathcal{M}}((G,k,O),T_{i})\) for each \(i\)). If \(T\) is a minimal solution for \((G,k,O)\), then \(T\in\mathcal{N}_{\mathcal{M}}((G,k,O),\mathbb{O})\) and the expected sequence \((T_{i})_{1\leq i\leq p}\) reduces to \(T_{1}=T\). Otherwise, there exists an \(S\in\textsc{Sol}_{\mathcal{M}}(G,k,O)\) and a non-empty set of transformations, say \(S^{\prime}\cup\{t\}\), such that \(T=S\cup S^{\prime}\cup\{t\}\) and there is no solution for \(G\) between \(S\) and \(S\cup S^{\prime}\cup\{t\}\). This entails that \(S^{\prime}\) is a minimal solution for \(\big{(}(S\cup\{t\})(G),k-|S|-1\big{)}\) and, as a consequence, \(T\in\mathcal{N}_{\mathcal{M}}((G,k,O),S)\) (see lines 4-5 of Algorithm 3). The conclusion follows from the induction hypothesis that guarantees the existence of solutions \(S_{1},\ldots,S_{q}\) such that \(S_{1}\in\mathcal{N}_{\mathcal{M}}((G,k,O),\mathbb{O})\)  
Figure 1: Structure of Algorithm 2. \(S_{i+1}\in\mathcal{N}_{\mathcal{M}}((G,k,O),S_{i})\) and \(S_{q}=S\). The expected sequence \(T_{1},\ldots,T_{p}\) for \(T\) is nothing but \(S_{1},\ldots,S_{q},T\). To conclude, it remains to show that Algorithm 3 is FPT.