# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 2 Enumerating Minimal Perfect Roman Domination
Since \(g(p_{j})=1\), this contradicts Condition 2 of Theorem 1 and \(g\) is not a minimal perfect Roman dominating function. Hence, \(\phi\) is a solution to the Sat instance. This proves that we have described a valid polynomial-time computable reduction and hence we have shown NP-hardness. Membership in NP is easy by a guess-and-check approach. This concludes the proof of Theorem 2. We use Theorem 1 also to obtain the announced polynomial-delay enumeration algorithm. This algorithm uses the idea that there is a bijection between all minimal perfect Roman dominating functions and all minimal Roman dominating functions of a graph. To show this bijection, we need the following characterization theorem from [23]. **Theorem 3**. : _Let \(G=(V,E)\) be a graph, \(f:V\to\{0,1,2\}\) be a function and let \(G^{\prime}\coloneqq G[V_{0}(f)\cup V_{2}(f)]\). Then, \(f\) is a minimal Roman dominating function if and only if the following holds:_  
1. \(N_{G}[V_{2}(f)]\cap V_{1}(f)=\emptyset\)_._
2. \(\forall v\in V_{2}(f):P_{G^{\prime},V_{2}(f)}(v)\
subseteq\{v\}\)_._
3. \(V_{2}(f)\) _is a minimal dominating set on_ \(G^{\prime}\)_._  
Let \(G=(V,E)\) be a graph. Define the following sets of functions:  
\(\mu\)-\(\mathcal{RDF}(G)=\{f:V\to\{0,1,2\}\mid f\) is a minimal Roman dominating function \(\}\) and  
\(\mu\)-\(\mathcal{PRDF}(G)=\{f:V\to\{0,1,2\}\mid f\) is a minimal perfect Roman dominating function \(\}\). **Theorem 4**. : _Let \(G=(V,E)\) be a graph. There is a bijection \(B\colon\mu\)-\(\mathcal{RDF}(G)\to\mu\)-\(\mathcal{PRDF}(G)\). Furthermore, \(B(f)\) and \(B^{-1}(g)\) can be computed in polynomial time (with respect to \(G\)) for each \(f\in\mu\)-\(\mathcal{RDF}(G)\) and \(g\in\mu\)-\(\mathcal{PRDF}(G)\)._  
Proof. : Let \(f\in\mu\)-\(\mathcal{RDF}(G)\) and \(g\in\mu\)-\(\mathcal{PRDF}(G)\). Define \(B(f)\) by the three sets  
\[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]1 \[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]2  
By the definition of \(B\), \(|N_{G}(v)\cap V_{2}(f)|=1\) holds for all \(v\in V_{0}(B(f))\). Since each \(v\in V\) with \(f(v)=2\) needs a private neighbor except itself by Theorem 3, \(N_{G}(v)\cap V_{0}(B(f))\
eq\emptyset\)holds. As any \(v\in V_{1}(f)\) has no neighbor in \(V_{2}(f)\) and any \(v\in V_{1}(B(f))\setminus V_{1}(f)\) has at least two neighbors in \(V_{2}(f)\), all conditions of Theorem 1 are met. Therefore, \(B(f)\in\mu\)-\(\mathcal{PRDF}(G)\). Define \(B^{-1}(g)\) by the three sets  
\[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]3 \[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]4  
By the definition of \(B^{-1}\), \(N_{G}(v)\cap V_{2}(B^{-1}(g))=\emptyset\) for each \(v\in V_{1}(B^{-1}(g))\). By Theorem 1, each \(v\in V_{0}(g)\) has exactly one neighbor in \(V_{2}(g)\). Therefore, each vertex in \(V_{0}(B^{-1}(g))\) has a neighbor in \(V_{2}(B^{-1}(g))\), and \(V_{2}(B^{-1}(g))\) is a dominating set on \(G[V_{0}(B^{-1}(g))\cup V_{2}(B^{-1}(g))]\). Theorem 1 implies that each \(v\in V_{2}(g)\) has a \(u\in N_{G}(v)\cap V_{0}(g)\) with \(\{v\}=N_{G}(u)\cap V_{2}(g)\). Hence, \(u\) is a private neighbor of \(v\) and \(B^{-1}(g)\in\mu\)-\(\mathcal{RDF}(G)\). This leaves to show that \(B^{-1}(B(f))=f\) and \(B(B^{-1}(g))=g\). Trivially,  
\[E\coloneqq \{\{v_{i},w_{i}\},\{\overline{v_{i}},w_{i}\},\{v_{i},y_{i}\},\{ \overline{v_{i}},y_{i}\},\{z_{i},y_{i}\}\ |\ i\in[n]\}\cup\]5  
holds. Let \(v\in V_{1}(f)\). By Theorem 3, we know \(N_{G}(v)\cap V_{2}(f)=\emptyset\). This implies \(v\in V_{1}(B(f))\cap V_{1}(B^{-1}(B(f)))\). Let \(v\in V_{0}(f)\) with \(|N_{G}(v)\cap V_{2}(f)|=1\). Thus, \(v\in V_{0}(B(f))\cap V_{0}(B^{-1}(B(f)))\). Let \(v\in V_{0}(f)\) with \(|N_{G}(v)\cap V_{2}(f)|\geq 2\). Therefore, \(v\in V_{1}(B(f))\) holds.