# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 2 Enumerating Minimal Perfect Roman Domination
Theorem 2: Extension Perfect Roman Domination _is NP-complete even on bipartite graphs of maximum degree 4._  
Proof: For the NP-hardness result, we employ Monotone 3-Sat-(2,2). So, let \(X:=\{x_{1},\ldots,x_{n}\}\) be the set of variables and \(C:=\{c_{1},\ldots,c_{m}\}\) the set of clauses. To simplify the notation, denote \(X^{\prime}=\{x_{i},\overline{x_{i}}\ |\ i\in[n]\}\). For each \(j\in[m]\), let \(c_{j}=l_{j1}\lor l_{j2}\lor l_{j3}\in C\) with \(l_{j1},l_{j2},l_{j3}\in X^{\prime}\). Define \(G=(V,E)\) with  
\[V\coloneqq \{v_{i},\overline{v_{i}},w_{i},y_{i},z_{i}\ |\ i\in[n]\}\cup\{p_{j},q_{j},r_{j}\ |\ j\in[m]\}\] \[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\] \[\{\{v_{i},p_{j}\}\ |\ j\in[m],k\in[3],i\in[n],x_{i}=l_{jk}\}\cup\] \[\{\{\overline{v_{i}},p_{j}\}\ |\ j\in[m],k\in[3],i\in[n], \overline{x_{i}}=l_{jk}\}\cup\] \[\{\{q_{j},p_{j}\},\{q_{j},r_{j}\}\ |\ j\in[m]\}.\]  
The gadgets are also depicted in Figure 1. Furthermore, let  
\[f\coloneqq 2\cdot\chi_{\{q_{j}|j\in[m]\}\cup[y_{j}|i\in[n]]}+\chi_{\{p_{j}|j\in[m] \}}\in\{0,1,2\}^{V}\,.\]  
Clearly, \(G\) can be constructed in polynomial time. Furthermore, the sets \(A\coloneqq\{v_{i},\overline{v_{i}},z_{i}\ |\ i\in[n]\}\cup\{q_{j}\ |\ j\in[m]\}\) and \(B\coloneqq\{w_{i},y_{i}\ |\ i\in[n]\}\cup\{p_{j},r_{j}\ |\ j\in[m]\}\) are partition classes. This is easy to observe, as in each of the edges, we mention first the element of \(A\) and then the one of \(B\). Since we consider Monotone 3-Sat-(2,2), for all \(i\in[n]\), \(j\in[m]\)  
\[\deg(r_{j}) =\deg(z_{i})=1<\deg(w_{i})=\deg(q_{j})=2<\deg(y_{i})=3\] \[< \deg(v_{i}) =\deg(\overline{v_{i}})=\deg(p_{j})=4.\]  
**Claim 1**. : _There is an assignment \(\phi\) satisfying \(C\) if and only if there is a minimal perfect Roman dominating function \(g\in\{0,1,2\}^{V}\) with \(f\leq g\)._  
Figure 1: Construction for Theorem 2. Proof. : Let \(\phi\) be an assignment satisfying the clauses. Then, define  
\[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\]0  
Trivially, \(f\leq g\). For \(j\in[m]\), \(r_{j}\in V_{0}(g)\) is only dominated by \(q_{j}\in V_{2}(g)\). Let \(i\in[n]\). Observe that \(z_{i}\in V_{0}(g)\) and that \(N(z_{i})\cap V_{2}(g)=\{y_{i}\}\). The last type of vertex to discuss in \(V_{0}(g)\) is \(w_{i}\). If \(\phi(x_{i})=1\), \(w_{i}\) is only dominated by \(v_{i}\). For \(\phi(x_{i})=0\), \(N(w_{i})\cap V_{2}(g)=\{\overline{v_{i}}\}\). Hence, the first condition of Theorem 1 is fulfilled. In order to see the validity of the second condition, let \(j\in[m]\). Assume \(c_{j}\) includes only positive literals (otherwise, the proof is analogous). Since \(\phi\) is a solution to the SAT instance, there exists \(x_{i}\in c_{j}\) with \(\phi(x_{i})=1\), which implies \(|N(p_{j})\cap V_{2}(g)|\geq 2\). As \(V_{1}(g)=\{p_{j}\mid j\in[m]\}\), the second condition is also satisfied. This leaves us to show the last condition. For each \(j\in[m]\), \(N(r_{j})\cap V_{2}(g)=\{q_{j}\}\). Let \(i\in[n]\). The vertex \(z_{i}\) is a private neighbor of \(y_{i}\in V_{2}(g)\). Since \(\phi\) is an assignment, \(w_{i}\) is the private neighbor of the vertex in \(V_{2}(g)\cap\{v_{i},\overline{v_{i}}\}\). Hence, \(g\) is a minimal perfect Roman dominating function. For the reverse direction, assume there is a minimal perfect Roman dominating function \(g\in\{0,1,2\}^{V}\) with \(f\leq g\). Observe that \(V\setminus N(V_{2}(f))=\{w_{i}\mid i\in[n]\}\). Because each vertex in \(V_{2}(g)\) needs to have a private neighbor, \(V_{2}(g)\setminus V_{2}(f)\subseteq\{v_{i},\overline{v_{i}}\mid i\in[n]\}\). For any \(i\in[n]\), \(\{v_{i},\overline{v_{i}}\}\
subseteq V_{2}(g)\). Otherwise, \(v_{i}\) would not have a private neighbor. Define \(\phi\coloneqq\chi_{\{x_{i}|i\in[n],g(v_{i})=2\}}\). Assume there is a clause \(c_{j}\) which is not satisfied by \(\phi\). Then, \(q_{j}\) is the only neighbor of \(p_{j}\) in \(V_{2}(g)\).