# Parameterised Enumeration for Modification Problems +
## 3 Enumeration of Graph Modification Problems with Ordering
### Size Ordering  
A common strategy in the enumeration context consists of defining a notion of a neighbourhood that allows to compute a new solution from a previous one with small amounts of computation time (see, e.g., the work of [PERSON] and [PERSON] [31]). We introduce the notion of a neighbourhood function, which, roughly speaking, generates some initial solutions from which all solutions can be produced. A priority queue then takes care of the ordering and avoids duplicates, which may require exponential space. For the graph modification problems of interest, we show that if the inclusion-minimal solutions can be generated in FPT, then such a neighbourhood function exists, accordingly providing a DelayFPT-enumeration algorithm. In the following, \(\mathbb{O}\) (the \"seed\") is a technical symbol that will be used to generate the initial solutions. **Definition 9**. : _Let \(\mathcal{M}\) be a graph modification problem. A neighbourhood function for \(\mathcal{M}\) is a (partial) function \(\mathcal{N}_{\mathcal{M}}\colon I_{\mathcal{M}}\times(\mathcal{S}_{\mathcal{M }}\cup\{\mathbb{O}\})\to 2^{\mathcal{S}_{\mathcal{M}}}\) such that the following holds:_  
1. _For all_ \(x=(G,k,O)\in I_{\mathcal{M}}\) _and_ \(S\in\mathrm{Sol}_{\mathcal{M}}(x)\cup\{\mathbb{O}\}\)_,_ \(\mathcal{N}_{\mathcal{M}}(x,S)\) _is defined._
2. _For all_ \(x\in I_{\mathcal{M}}\)_,_ \(\mathcal{N}_{\mathcal{M}}(x,\mathbb{O})=\emptyset\) _if_ \(\mathrm{Sol}_{\mathcal{M}}(x)=\emptyset\)_, and_ \(\mathcal{N}_{\mathcal{M}}(x,\mathbb{O})\) _is an arbitrary set of solutions otherwise._
3. _For all_ \(x\in I_{\mathcal{M}}\) _and_ \(S\in\mathrm{Sol}_{\mathcal{M}}(x)\)_, if_ \(S^{\prime}\in\mathcal{N}_{\mathcal{M}}(x,S)\) _then_ \(|S|<|S^{\prime}|\)_._
4. _For all_ \(x\in I_{\mathcal{M}}\) _and all_ \(S\in\mathrm{Sol}_{\mathcal{M}}(x)\)_, there exists_ \(p>0\) _and_ \(S_{1},\ldots,S_{p}\in\mathrm{Sol}_{\mathcal{M}}(x)\) _such that (i)_ \(S_{1}\in\mathcal{N}_{\mathcal{M}}(x,\mathbb{O})\)_, (ii)_ \(S_{i+1}\in\mathcal{N}_{\mathcal{M}}(x,S_{i})\) _for_ \(1\leq i<p\) _and (iii)_ \(S_{p}=S\)_._  
_Furthermore, we say that \(\mathcal{N}_{\mathcal{M}}\) is FPT computable, when \(\mathcal{N}_{\mathcal{M}}(x,S)\) is computable in time \(f(\kappa(x))\cdot\text{poly}(|x|)\) for any \(x\in I_{\mathcal{M}}\) and \(S\in\mathrm{Sol}_{\mathcal{M}}(x)\)._  
As a result, a neighbourhood function for a problem \(\mathcal{M}\) is a function that in a first phase computes from scratch an initial set of solutions (see Definition 9(2)). In many of our applications below, \(\mathcal{N}_{\mathcal{M}}(x,\mathbb{O})\) will be the set of all minimal solutions for \(x\). In a second phase these solutions are iteratively extended (see condition (3)), where condition (4) guarantees that we do not miss any solution, as we will see in the next theorem. **Theorem 1**. : _Let \(\mathcal{M}\) be a graph modification problem. If \(\mathcal{M}\) admits a neighbourhood function \(\mathcal{N}_{\mathcal{M}}\) that is FPT-computable, then \(\textsc{Enum-}\mathcal{M}^{\mathrm{SIZE}}\in\mathrm{DelayFPT}\)._  
Proof. : Algorithm 2 outputs all solutions in DelayFPT time. By the definition of the priority queue (recall in particular that insertion of an element is done only if the element is not yet present in the queue) and by the fact that all elements of \(\mathcal{N}_{\mathcal{M}}((G,k,O),S)\) are of bigger size than \(S\) by Definition 9(3), it is easily seen that the solutions are output in the right order and that no solution is output twice. Besides, no solution is omitted. Indeed, given \(S\in\mathrm{Sol}_{\mathcal{M}}(G,k,O)\) and \(S_{1},\ldots,S_{p}\) associated with \(S\) by Definition 9(4), we prove by induction that each \(S_{i}\) is inserted in \(Q\) during the run of the algorithm:  
1. This proceeds from line 2 of the algorithm. 2. The solution \(S_{i-1}\) is inserted in \(Q\) by induction hypothesis and hence all elements of \(\mathcal{N}_{\mathcal{M}}((G,k,O),S_{i-1})\), including \(S_{i}\), are inserted in \(Q\) (line 5 of Algorithm 2).