# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 4 Parameterized Complexity
### Clique Width and Treewidth  
The clique width of a graph \(G\) (cwd\((G)\) for short) denotes the minimum number of labels needed to construct \(G\) with the following operations:  
1. Create a graph of one isolate vertex. 2. Build the disjoint union of two labeled graphs. 3. Connect each vertex with label \(i\) with each vertex of label \(j\) by an edge. 4. Relabel vertices with label \(i\) to \(j\). Recall that \(\text{LinEMSOL}(\tau_{1})\) refers to the possibility to formulate an optimization problem using a linear function of the cardinalities of sets that realize the free set variables, while \(\tau_{1}\) restricts the vocabulary of the monadic second-order logic to vertex set variables, with adjacency as the only relation. We want to employ this logic next. First, we give a \(\text{LinEMSOL}(\tau_{1})\) formula for the optimization problems corresponding to Perfect Roman Domination and to Unique Response Roman Domination in order to show that these are linear-time FPT if parameterized by cwd, using now classical results from [39; 40]. cwd is an interesting parameter since an FPT algorithm with cwd as the parameter implies FPT algorithms with respect to tw, nd, or vc as parameters. However, the algorithmic results of the previous section do not follow from these considerations, as it is known that even unit interval graphs have unbounded clique width; see [40]. Lemma 4: Minimum Perfect Roman Domination _on the graph \(G=(V,E)\) can be expressed as_  
\[\operatorname*{argmin}_{X_{1}\subseteq V,X_{2}\subseteq V}\left\{|X_{1}|+2|X_{ 2}|\mid\left\langle G,X_{1},X_{2}\right\rangle\right\},\text{ with }\theta(X_{1},X_{2})\text{ equal to}\]  
\[\forall v(X_{1}(v)\lor X_{2}(v)\vee\exists u[X_{2}(u)\wedge E(v,u)\wedge\forall w ([X_{2}(w)\wedge E(w,v)]\Rightarrow u=w)])\,.\]  
Proof: Let \(G=(V,E)\) be a graph for which we want to determine the perfect Roman dominating function of the smallest weight. First, if \(f\) is some perfect Roman dominating function of \(G\), then \(\theta(V_{1}(f),V_{2}(f))\) is obviously true. Now, we want to show why \(X_{1},X_{2}\subseteq V\), as a minimum solution would describe a perfect Roman dominating function. Define \(f\coloneqq\chi_{X_{1}}+2\chi_{X_{2}}\). We can then see that for all \(v\in V\), we have either \(v\in X_{1}\), or \(v\in X_{2}\), or there exists a \(u\in X_{2}\cap N(v)\) such that there is no other neighbor of \(v\) in \(X_{2}\). Therefore, we only need to show \(X_{1}\cap X_{2}=\emptyset\). So, assume there is a \(v\in X_{1}\cap X_{2}\). Then, for \(X_{1}^{\prime}\coloneqq X_{1}\setminus\{v\}\), \((X_{1}^{\prime},X_{2})\) is a smaller solution: \(v\) is still in \(X_{2}\), which does not change. Hence, \(f\) is a perfect Roman dominating function. **Theorem 14**. : _cwd-Perfect Roman Domination is in FPT if we assume the clique decomposition given as part of the input. Furthermore, Perfect Roman Domination can be solved in linear time on distance-hereditary graphs._  
Proof. : As already noted, the first claim follows from Lemma 4. [PERSON] and [PERSON] showed in [40] that distance-hereditary graphs have a clique width bounded by three, which gives the second claim. **Theorem 15**. : _tw-Perfect Roman Domination is in FPT._  
Proof. : First, given a graph \(G=(V,E)\), it is possible to compute an optimal tree decomposition in FPT-time, parameterized by the treewidth of the graph. Then, we can apply [PERSON]'s theorem that allows to conclude our result, as we have provided an MSO formula for our property. With similar techniques, we can also prove an analogous result for Unique Response Roman Domination. **Theorem 16**. : _cwd-Unique Response Roman Domination is in FPT if we assume the clique decomposition given as part of the input._  
Proof. : For Unique Response Roman Domination, we have to make sure that there is no vertex of value 1 or 2 in the neighborhood of any vertex of value 2.