# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 4 Parameterized Complexity
### Solution Size
Since \(C_{v}\) is a clique of true twins, \(N_{\widetilde{G}}(v_{j})\cap V_{2}(f)=\emptyset\) and \(f(v_{j})=1\) for each \(j\in[2k+1]\). Hence, \(|V_{1}(f)|>2k\). This contradicts \(\omega(f)\leq 2k\). Therefore, \(V_{1}(f)=\emptyset\). Define \(D\coloneqq\{v\in V\mid v_{1}\in V_{2}(f)\}\). If there is a \(v\in V\) with \(N[v]\cap D=\emptyset\), \(f\) would not be a Roman dominating function, as \(v_{1}\) is not dominated. The existence of a \(v\in V\) with \(|N[v]\cap D|\geq 2\) would contradict the fact that \(f\) is unique response Roman dominating function, as either \(v_{1}\in V_{2}(f)\) and \(v_{1}\) has a neighbor in \(V_{2}(f)\), or \(v_{1}\) has two neighbors in \(V_{2}(f)\). In total, \(D\) is a perfect code. Now, we will sketch the \(\mathsf{W}[1]\)-membership proof by using Steps-STMC. To this end, let \(G=(V,E)\) be a graph of order \(n\) and \(k\in\mathbb{N}\). The Turing machine will work in four phases as follows, assuming it was provided with some basic arithmetic capabilities by the reduction machine as detailed in the proof of Theorem 4.1:  
1. Guess the vertices in \(V_{2}(f)\) and then \(V_{1}(f)\). We split the vertices via a special symbol \(\zeta\) (this takes at most \(2k+1\) steps). 2. Check if vertices in \(V_{2}(f)\) have distance 2 to the vertices in \(V_{1}(f)\) and distance 3 to the vertices in \(V_{2}(f)\) (in at most \(\frac{k(k+1)}{2}\) steps). If this is the case, then the machine stops in a non-final state. 3. Check if we enumerated vertices in \(V_{1}(f)\) twice (in at most \(\frac{k(k+1)}{2}\) steps). If this is the case, then the machine stops in a non-final state. 4. If \(|V_{1}(f)|+\sum_{v\in V_{2}(f)}|N[v]|=|V|\), then \(f\) is a minimal unique response Roman dominating function (as each vertex is only dominated once). This can be computed in \(k\) steps. This concludes the proof of Theorem 4.2. The previous \(\mathsf{W}[1]\)-hardness result could also be used to show that \(\omega(f)\)-Perfect Roman Domination is \(\mathsf{W}[1]\)-complete. We can show this type of result even on bipartite graphs. Theorem 4.2.: \(\omega(f)\)-Perfect Roman Domination _is \(\mathsf{W}[1]\)-complete even on bipartite graphs._  
Proof. : For membership, we refer to Theorem 4.2. For the hardness, we use Perfect Code. Let \(G=(V,E)\) be a graph and \(k\in\mathbb{N}\). Define \(\widetilde{G}\coloneqq(\widetilde{V},\widetilde{E})\) with \(V^{\prime}\coloneqq\{v_{i}^{\prime}\mid v\in V,i\in[2k+3]\},Y:=\{y_{1},\ldots, y_{2k+3}\},Z\coloneqq\{z_{1},\ldots,z_{2k+3}\}\), giving  
\[\sum_{u\in V_{1}(f)}(1-|N(u)\cap V_{2}(f)|) =|V_{1}(f)|-\sum_{u\in V_{1}(f)}\sum_{v\in V_{2}(f)}\chi_{E}(\{u, v\})\]1 \[\sum_{u\in V_{1}(f)}(1-|N(u)\cap V_{2}(f)|) =|V_{1}(f)|-\sum_{u\in V_{1}(f)}\sum_{v\in V_{2}(f)}\chi_{E}(\{u, v\})\]2 \[\sum_{u\in V_{1}(f)}(1-|N(u)\cap V_{2}(f)|) =|V_{1}(f)|-\sum_{u\in V_{1}(f)}\sum_{v\in V_{2}(f)}\chi_{E}(\{u, v\})\]3  
\(\widetilde{G}\) is visualized in \[\sum_{u\in V_{1}(f)}(1-|N(u)\cap V_{2}(f)|) =|V_{1}(f)|-\sum_{u\in V_{1}(f)}\sum_{v\in V_{2}(f)}\chi_{E}(\{u, v\})\]4 \(\widetilde{G}\) is bipartite with the classes \(A\coloneqq V\cup Y\cup Z\) and \(B\coloneqq\{x\}\cup V^{\prime}\) (the edges are written in such a way that the vertices from \(A\) are mentioned first). Furthermore, \(\widetilde{G}\) has \((2k+3)\cdot(|V|+2)+|V|+1\) many vertices. This leaves us to show that \(G\) has a perfect code of size at most \(k\) if and only if \(\widetilde{G}\) has a perfect Roman dominating function with weight at most \(2k+2\). Assume there is a perfect code \(D\subseteq V\) with \(|D|\leq k\). Then, define \(f\coloneqq 2\cdot\chi_{D\cup\{x\}}\). \(V\cup\{x\}\cup Y\cup Z\) is dominated by \(x\). If there were a \(v_{i}^{\prime}\in V^{\prime}\) which is not dominated by \(f\), then \(v\) would not be dominated in \(G\) by \(D\). Therefore, \(f\) is a Roman dominating function. Further \(N(Y\cup Z)\cap V_{2}(f)=\{x\}\). For any \(i\in[2k+3]\) and \(v\in V\), \(v_{i}^{\prime}\) has only one neighbor in \(V_{2}(f)\), as \(Y\subseteq V_{0}(f)\) and, otherwise, \(v\) would be dominated twice by \(D\).