# Parameterised Enumeration for Modification Problems +
## 2 Preliminaries
### Graph Modification Problems  
Graph modification problems have been studied for a long time in computational complexity theory [26]. Already in the monograph by [PERSON] and [PERSON] [27], among the graph-theoretic problems considered, many fall into this problem class. To the best of our knowledge, graph modification problems were studied in the context of parameterised complexity for the first time in [28]. In this paper, we consider only undirected graphs. Let \(\mathcal{G}\) denote the set of all undirected graphs. A graph property \(\mathcal{P}\subseteq\mathcal{G}\) is a set of graphs. Given a graph property \(\mathcal{P}\) and an undirected graph \(G\), we write \(G\models\mathcal{P}\) if the graph \(G\) obeys the property \(\mathcal{P}\), that is, \(G\in\mathcal{P}\). **Definition 6** (Graph Operations). : _A graph operation for \(G\) is either of the following:_  
* _removing a vertex:_ \(A\) _function_ \(\mathrm{rem}_{v}\colon\mathcal{G}\to\mathcal{G}\) _such that_ \(\mathrm{rem}_{v}(G)\) _is the graph obtained by removing the vertex_ \(v\) _from_ \(G\) _(if_ \(v\) _is present; otherwise_ \(\mathrm{rem}_{v}\) _is the identity) and deleting all incident edges to_ \(v\)_,_
* _adding/removing an edge:_ \(A\) _function_ \(\mathrm{add}_{\{u,v\}},\mathrm{rem}_{\{u,v\}}\colon\mathcal{G}\to\mathcal{G}\) _such that_ \(\mathrm{add}_{\{u,v\}}(G)\)_,_ \(\mathrm{rem}_{\{u,v\}}(G)\) _is the graph obtained by adding/removing the edge_ \(\{u,v\}\) _to_ \(G\) _if_ \(u\) _and_ \(v\) _are present in_ \(G\)_; otherwise both functions are the identity_ _Two operations_ \(o,o^{\prime}\) _are dependent if_
* \(o=\mathrm{rem}_{v}\) _and_ \(o^{\prime}=\mathrm{rem}_{\{u,v\}}\) _(o removes the vertex_ \(v\) _and_ \(o^{\prime}\) _removes an edge incident to_ \(v\)_) or_
* \(o=\mathrm{rem}_{\{u,v\}}\) _and_ \(o^{\prime}=\mathrm{add}_{\{u,v\}}\) _(o removes the edge_ \(\{u,v\}\) _and_ \(o^{\prime}\) _adds the same edge_ \(\{u,v\}\) _again)._  
_A set of operations is consistent if it does not contain two dependent operations. Given such a consistent set of operations \(S\), the graph obtained from \(G\) by applying the operations in \(S\) on \(G\) is denoted by \(S(G)\)._  
Now, we turn towards the definition of solutions and will define minimality in terms of being inclusion-minimal. **Definition 7** (Solutions). : _Given a graph property \(\mathcal{P}\), a graph \(G\), \(k\in\mathbb{N}\) and a set of operations \(O\), we say that \(S\) is a solution for \((G,k,O)\) with respect to \(\mathcal{P}\) if the following three properties hold:_  
1. \(S\subseteq O\) _is a consistent set of operations,_
2. \(|S|\leq k\) _and_
3. \(S(G)\models\mathcal{P}\)_._  
_A solution \(S\) is minimal if there is no solution \(S^{\prime}\) such that \(S^{\prime}\subsetneq S\)._[PERSON] [28] was interested in the following parameterised graph modification decision problem with respect to a given graph property \(\mathcal{P}\): \begin{tabular}{l l} \hline \hline
**Problem:** & \(\mathcal{M}_{\mathcal{P}}\) \\ \hline
**Input:** & \((G,k,O)\), \(G\) undirected graph, \(k\in\mathbb{N}\), \(O\) set of operations on \(G\). \\
**Parameter:** & The integer \(k\). \\
**Question:** & Does there exist a solution for \((G,k,O)\) with respect to \(\mathcal{P}\)? \\ \hline \hline \end{tabular}   
Some of the most important examples of graph modification problems are presented now. A chord in a graph \(G=(V,E)\) is an edge between two vertices of a cycle \(C\) in \(G\) which is not part of \(C\). A given graph \(G=(V,E)\) is triangular (or chordal) if each of its induced cycles of four or more nodes has a chord. The problem Triangulation then asks, given an undirected graph \(G\) and \(k\in\mathbb{N}\), whether there exists a set of at most \(k\) edges such that adding this set of edges to \(G\) makes it triangular [PERSON] showed that this problem is NP complete [15]. [PERSON] et al. [29] and independently [PERSON] [28] have shown that the parameterised problem is in FPT.