# Parameterised Enumeration for Modification Problems +
## 3 Enumeration of Graph Modification Problems with Ordering
### Lexicographic Ordering  
We first prove that, for any graph property \(\mathcal{P}\), if the decision problem \(\mathcal{M}_{\mathcal{P}}\) is in FPT then there is an efficient enumeration algorithm for Enum-\(\mathcal{M}_{\mathcal{P}}^{\text{LEX}}\). **Lemma 1**: _Let \(\mathcal{M}_{\mathcal{P}}\) be a graph modification problem. If \(\mathcal{M}_{\mathcal{P}}\) is in FPT then Enum-\(\mathcal{M}_{\mathcal{P}}^{\text{LEX}}\in\text{DelayFPT}\) with polynomial space._  
**Proof. ** Algorithm 1 enumerates all solutions of an instance of a given modification problem \(\mathcal{M}_{\mathcal{P}}\) by the method of self-reducibility (it is an extension of the flash light search of Creignou and Hebrard [7]). The algorithm uses a function \(\mathtt{ExistsSol}(G,k,O)\) that tests if the instance \((G,k,O)\) of the modification problem \(\mathcal{M}_{\mathcal{P}}\) has a solution. By the assumption of the lemma, \(\mathcal{M}_{\mathcal{P}}\in\text{FPT}\) so this function runs in FPT time. We use calls to this function to avoid exploration of branches of the recursion tree that do not lead to any output. Moreover, we ensure that the solutions using \(o_{p}\) have to be consistent. This consistency check runs in polynomial time for graph operations. The rest yields a search tree of depth at most \(k\). From this it follows that, for any instance of length \(n\), the time beween the output of any two solutions is bounded by \(f(k)\cdot p(n)\) for some polynomial \(p\) and a computable function \(f\). ```
Input:\((G,k,O)\): A graph \(G\), \(k\in\mathbb{N}\), an ordered set of operations \(O=\{o_{1},\ldots,o_{n}\}\) Output: all consistent sets \(S\subseteq O\) s.t. \(|S|\leq k\), \(S(G)\models\mathcal{P}\) in lexicographic order
1 if\(\mathtt{ExistsSol}(G,k,O)\)then\(\mathtt{Generate}(G,k,O,\emptyset)\); ProcedureGenerate\((G,k,O,S)\):
2 if\(O=\emptyset\) or \(k=0\)thenreturn\(S\);
3 else
4 let \(o_{p}\) be the lexicographically last operation in \(O,O^{\prime}:=O\setminus\{o_{p}\}\);
5 if\(\mathtt{ExistsSol}(S(G),k,O^{\prime})\)then\(\mathtt{Generate}(S(G),k,O^{\prime},S)\);
6 if\(S\cup\{o_{p}\}\) is consistent and \(\mathtt{ExistsSol}((S\cup\{o_{p}\})(G),k-1,O^{\prime})\)then
7 Generate\(((S\cup\{o_{p}\})(G),k-1,O^{\prime},S\cup\{o_{p}\})\). ```  
**Algorithm 1**Enumerate all solutions of \(\mathcal{M}_{\mathcal{P}}\) in lexicographic order  
**Corollary 1**: Enum-Triangulation\({}^{\text{LEX}}\in\text{DelayFPT}\) with polynomial space. **Proof. ** [PERSON] et al. [29] and [PERSON] [28] showed that Triangulation\(\in\text{FPT}\). Now, by applying Lemma 1, we get the result. [PERSON] [28] identified a class of graph properties whose associated modification problems belong to FPT. Let us introduce some terminology. **Definition 8**: _Given two graphs \(G=(V,E)\) and \(H=(V^{\prime},E^{\prime})\), we write \(H\trianglelefteq G\) if \(H\) is an induced subgraph of \(G\), i.e., \(V^{\prime}\subseteq V\) and \(E^{\prime}=E\cap(V^{\prime}\times V^{\prime})\). Let \(\mathcal{F}\) be a set of graphs and \(\mathcal{P}\) be a graph property. We say that \(\mathcal{F}\) is a forbidden set characterisation of \(\mathcal{P}\) if for any graph \(G\) it holds that: \(G\models\mathcal{P}\) iff for all \(H\in\mathcal{F},H\
ot\trianglelefteq G\)._  
Among the problems presented in the previous section (see page 3.2), Triangle-Deletion and Cluster-Editing have a finite forbidden set characterisation, namely by triangles and paths of length two. In contrast to that, Triangulation has a forbidden set characterisation which is infinite, since cycles of arbitrary length are problematic. Actually, for properties having a finite forbidden setcharacterisation, the corresponding modification problem is fixed-parameter tractable. Together with Lemma 1, this provides a positive result in terms of enumeration. **Proposition 1** ([28]). : _If a property \(\mathcal{P}\) has a finite forbidden set characterisation then \(\mathcal{M}_{\mathcal{P}}\) is in FPT._  
**Corollary 2**.