# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 2 Enumerating Minimal Perfect Roman Domination  
The main goal of this section is to find a polynomial-delay algorithm to enumerate all minimal perfect Roman dominating functions even when solving the extension problem is hard, which blocks the standard approach to obtaining such enumeration algorithms. **Remark 1**. : _It should be mentioned that there are graphs \(G=(V,E)\) such that the set of perfect Roman dominating functions on \(G\) is not closed under \(\leq\). This means that there exists a perfect Roman dominating function \(f\in\{0,1,2\}^{V}\) and a \(g\in\{0,1,2\}^{V}\) with \(f\leq g\) such that \(g\) is no perfect Roman dominating function. One example of this is the 4-cycle_  
\[C_{4}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\{v_{3},v _{4}\},\{v_{4},v_{1}\}\})\]  
_with the two functions_  
\[ \begin{array}{llll}f(v_{1})=0,&f(v_{2})=2,&f(v_{3})=0,&f(v_{4})=1,\\ g(v_{1})=0,&g(v_{2})=2,&g(v_{3})=0,&g(v_{4})=2.\end{array} \]  
_This contradicts the idea of extension problems as they are defined in [25] because this violates the so-called upward closedness condition, but this condition is a matter of debate even in [25]._  
We often employ the following characterization result that is of independent interest. **Theorem 1**. : _Let \(G=(V,E)\) be a graph. A function \(f:V\to\{0,1,2\}\) is a minimal perfect Roman dominating function if and only if the following conditions are true:_  
1. \(\forall v\in V_{0}(f):\ |N_{G}(v)\cap V_{2}(f)|=1\)_._
2. \(\forall v\in V_{1}(f):\ |N_{G}(v)\cap V_{2}(f)|\
eq 1\)_._
3. \(\forall v\in V_{2}(f):\ |N_{G}(v)\cap V_{0}(f)|\
eq 0\)_._  
Proof. : Let \(f\) be a minimal perfect Roman dominating function. This implies the first condition. If there exists a \(v\in V_{1}(f)\) with \(|N_{G}(v)\cap V_{2}(f)|=1\), then \(f-\chi_{\{v\}}\) is also a perfect Roman dominating function, cf. Observation 2. For each \(v\in V_{2}(f)\), \(|N_{G}(v)\cap V_{0}(f)|\
eq 0\), as, otherwise, \(f-\chi_{\{v\}}\) is also a perfect Roman dominating function. Now assume \(f\) is a function that fulfills these conditions. By Condition 1, we know \(f\) is a perfect Roman dominating function. Let \(g\) be a minimal perfect Roman dominating function with \(g\leq f\). Thus, \(V_{0}(f)\subseteq V_{0}(g)\) and \(V_{2}(g)\subseteq V_{2}(f)\) hold. Assume there exists a \(v\in V\) with \(g(v)<f(v)=2\). By Condition 3, there exists some \(u\in N_{G}(v)\cap V_{0}(f)\). Because of condition 1, \(v\) is the only neighbor of \(u\) with value 2. Hence, \(N_{G}(u)\cap V_{2}(g)\subseteq N_{G}(u)\cap(V_{2}(f)\setminus\{v\})=\emptyset\). This contradicts the construction of \(g\) as a perfect Roman dominating function. Therefore, \(V_{2}(g)=V_{2}(f)\). If there were a \(v\in V\) with \(g(v)=0<1=f(v)\), then this would contradict that \(g\) is a perfect Roman dominating function since \(|N_{G}(v)\cap V_{2}(g)|=|N_{G}(v)\cap V_{2}(f)|\
eq 1\). **Remark 2**. : _This result implies that the constant function \(\chi_{V}\colon V\to\{0,1,2\},v\mapsto 1\) is the maximum minimal perfect Roman dominating function with respect to \(\omega\) for each graph \(G=(V,E)\), similar to maximum minimal Roman dominating functions as discussed in [26]. The reason is simple: if there exists a vertex \(v\in V\) of value \(2\), then this vertex needs a neighbor \(u\) with value \(0\)_Since \(u\) has exactly one neighbor in \(V_{2}(f)\), \(\omega(f)\leq|V|\) for each perfect Roman dominating function \(f\)._  
**Problem name:** Extension Perfect Roman Domination (Ext PRD)  
**Given:** A graph \(G=(V,E)\) and \(f\in\{0,1,2\}^{V}\). **Question:** Is there a minimal perfect Roman dominating function \(g\) on \(G\) with \(f\leq g\)? For the NP-hardness proof, we use Monotone 3-Sat-(2,2). This is a variant of 3-Sat where each clause includes only positive or negative literals and each variables appears twice positive and twice negative in clauses. It is known by [27] that also this restriction of 3-Sat is NP-complete.