# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 1 Introduction
**Problem name:** Perfect Roman Domination (PRD)  
**Given:** A graph \(G=(V,E)\) and \(k\in\mathbb{N}\)  
**Question:** Is there a perfect Roman dominating function \(f\) on \(G\) with \(\omega(f)\leq k\)? Let \(u_{R}(G)\) denote the smallest weight of any unique response Roman dominating function \(f\) on \(G\). Furthermore, \(\gamma_{R}^{p}(G)\) denotes the smallest weight of any perfect Roman dominating function on \(G\). The following is known about the complexity of these decision problems. Unique Response Roman Domination is NP-complete on regular bipartite graphs [18]. [PERSON] et al. [19] showed that it is NP-complete on chordal graphs, and polynomial-time solvable on distance-hereditary and interval graphs. They also proved that there is no Unique Response Roman Domination polynomial-time approximation algorithm within a factor of \(n^{1-e}\) for any constant \(e>0\) and any \(n\)-vertex input graph, if NP \(\
eq\) P. Perfect Roman Domination is NP-complete on chordal graphs, planar graphs, and bipartite graphs, and polynomial-time solvable on block graphs, cographs, series-parallel graphs, and proper interval graphs as shown in [20]. These results are complemented by our complexity results in this paper as surveyed in Table 1 that presents the main classical complexity results of our paper. Notice that, in particular, our results concerning split and chordal bipartite graphs solve questions posed as open in [19] (Table 1). We complement the NP-hardness results by providing FPT-algorithms for the parameters treewidth and solution size, as well as for the dual parameter, both for Perfect Roman Domination and for Unique Response Roman Domination. Also, if the clique decomposition is explicitly given, the problems can be solved in FPT-time when parameterized by the clique width of this decomposition. Enumeration is a wide area of research as testified by specialized workshops like [21]. For some examples, we refer to the survey [22]. From a practical point of view, enumeration can be interesting if not all aspects of the problem have been satisfactorily modeled. This also makes sense for the motivation of Roman Domination (variants). It could be the case that between neighbored regions, there is a conflict unknown to the strategic planner of the army deployment. Such a conflict could be a reason why the regions do not want to defend each other. Enumerating minimal Roman dominating functions was considered by [PERSON] et al. [23]. There, it was shown that all pointwise (i.e., for \(f,g:V\to\{0,1,2\}\), \(f\leq g\) if and only if \(f(v)\leq g(v)\) for all \(v\in V\)) minimal Roman dominating functions of a graph of order \(n\) can be enumerated in time \(\mathcal{O}(1.9332^{n})\) with _polynomial delay_. An enumeration algorithm has _polynomial delay_ if the time between two subsequent outputs of the algorithm can be bounded by some polynomial, as well as the time from the start to the first output and the time between the last output and the termination of the algorithm. This property is interesting if a user (or another program) processes the results in a pipeline fashion. Also, it is not known if there is such an algorithm for enumerating (inclusion-wise) minimal dominating sets. In this context, we remark the following. **Observation 1**. : _Unless \(P=NP\), there exists no polynomial-delay enumeration algorithm for (inclusion-wise minimal) perfect codes._  
Namely, such a polynomial-delay enumeration algorithm could also be used to decide (in polynomial time) if a perfect code exists in a given graph, a problem known to be NP-hard; see [24]. This contrasts with the polynomial-delay algorithms that we develop in this paper for enumerating minimal unique response and Perfect Roman Dominating Functions. We also obtain input-sensitive enumeration results in this way. We now collect more notation that we will use in the paper. Let \(\mathbb{N}\) denote the set of all non-negative integers (including \(0\)). For \(n\in\mathbb{N}\), we will use the notation \([n]\coloneqq\{1,\ldots,n\}\). Let \(A,B\) be two sets.