# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Chordal Bipartite Graphs
Since \(k\) is polynomial in \(n,m\), the graph can be constructed in polynomial time. This leaves us to show that \((\mathcal{X},\mathcal{C})\) is a yes-instance of the One-in-Three 3 SAT if and only if there is a perfect Roman dominating function \(f\) on \(G\) with \(\omega(f)\leq k\). To prove the NP-hardness for Unique Response Roman Domination, we show that if there is such an \(f\), then there is even a unique response Roman dominating function \(g\) with \(\omega(g)\leq k\). Let \(\phi\) be a solution of the One-in-Three 3 SAT instance. Then, define \(f\in\{0,1,2\}^{V}\) with  
\[v\mapsto \begin{cases}2,&\exists T\in\mathcal{V}^{\prime}:\,v=r_{T}\\ 2,&\exists(i,j)\in M^{\prime}:\,v\in\{a_{i,j},b_{i,j}\}\wedge\phi(x_{i})=1\\ 2,&\exists(i,j)\in M^{\prime}:\,v\in\{\overline{a}_{i,j},\overline{b}_{i,j}\} \wedge\phi(x_{i})=0\\ 0,&\text{else}\end{cases} \]  
Clearly, \(\omega(f)=2\cdot(m+n(m-1)+2 nm)+4 nm=k\). For each \(T\in\mathcal{V}^{\prime}\) and \(p\in[k]\), \(q[T,p],s[T,p]\) are only dominated by \(r_{T}\). By the definition of \(f\), for each \(i\in[n]\), the vertices in \(\{a_{i,j},b_{i,j},\overline{a}_{i,j},\overline{b}_{i,j},e_{i,j,p},f_{i,j,p}\mid j \in[m],p\in[k]\}\cup\{u_{i,j,p}\mid j\in[m-1],p\in[k]\}\) are dominated exactly once by either \(a_{i,j},b_{i,j}\), or \(\overline{a}_{i,j},\overline{b}_{i,j}\). Let \(j\in[m]\) and \(p\in[k]\). Since \(\phi\) is a solution, there is exactly one literal which fulfills \(\mathsf{C}_{j}\). Hence, there is exactly one neighbor of \(w_{j,p}\) in of value \(2\). Thus, \(f\) is a perfect Roman dominating function. Furthermore, it is even a unique response Roman dominating function. Now, let \(f\) be a minimal perfect Roman dominating function with \(\omega(f)=k\). Let \(T\in\mathcal{V}^{\prime}\) and \(p\in[k]\). Since \(s[T,p]\) is pendant, \(f(s[T,p])\
eq 0\) implies \(f(r[T])\
eq 2\). Otherwise, \(f\) would not be minimal (see Theorem 1, conditions 2 and 3). Hence, for each \(p^{\prime}\in[k]\), \(f(s[T,p])\
eq 0\) and \(\omega(f)>k\), as \(r[T]\) has to be dominated. Thus, for each \(T^{\prime}\in\mathcal{V}^{\prime}\) and \(p^{\prime}\in[k]\), \(f(s[T^{\prime},p])=0\) and \(f(r[T^{\prime}])=2\). If there is a \(v\in T\) with \(f(v)=2\), then \(f(q[T,p^{\prime}])\
eq 0 all \(i\in[n],j\in[m]\), to dominate \(\mathcal{E}_{i,j}\cup\mathcal{F}_{i,j}\), \(|V_{2}(f)\cap\{a_{i,j},\overline{a}_{i,j}\}|=1=|V_{2}(f)\cap\{b_{i,j},\overline{ b}_{i,j}\}|\) and \(f(a_{i,j})=f(b_{i,j})\
eq f(\overline{a}_{i,j})=f(\overline{b}_{i,j})\). Let \(i\in[n],j\in[m-1]\). Since \(u_{i,j,p}\) must be dominated exactly once, \(f(\overline{b}_{i,j+1})\
eq f(b_{i,j})\). Also, \(f(b_{i,j}),f(b_{i,j+1}),f(b_{i,j+1})\in\{0,2\}\), together with \(f(\overline{b}_{i,j+1})\
eq f(b_{i,j+1})\), implies \(f(b_{i,j})=f(b_{i,j+1})\). So, for each \(i\in[n]\) and \(j_{1},j_{2}\in[m]\), \(f(a_{i,j_{1}})=f(a_{i,j_{2}})\
eq f(\overline{a}_{i,j_{1}})=f(\overline{a}_{i,j_{2}})\). Define \(X_{1}\coloneqq\{x_{i}\mid i\in[n],\forall j\in[m]:f(a_{i,j})=2\}\) and the assignment \(\phi\coloneqq\chi_{X_{1}}\in\{0,1\}^{X}\). Let \(j\in[m]\). Since \(j\in[m],w_{j,p},q\{\mathcal{W}_{j},p\}\in V_{0}(f)\) for all \(p\in[k],N(w_{j,p})\cap\mathcal{A}\cap V_{2}(f)\) is not empty. Hence, there is a true literal satisfying \(C_{j}\). So, the given One-in-Three 3 SAT instance is a yes-instance. This completes the proof of Theorem 13.