# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 1 Introduction  
There are many ways to get along with NP-complete problems. For example, you could consider exponential-time algorithms or approximation algorithms. Here, we want to deal with Perfect Roman Domination and Unique Response Roman Domination by looking into enumeration, into the complexity of related decision problems in special graph classes, and into parameterized complexity. We only consider simple undirected graphs \(G=(V,E)\) throughout this paper. We recall some notions next. \(N_{G}(v)\coloneqq\{u\in V\mid uv\in E\}\) describes the _open neighborhood_ of \(v\in V\) with respect to \(G\). The _closed neighborhood_ of \(v\in V\) with respect to \(G\) is defined by \(N_{G}[v]\coloneqq N_{G}(v)\cup\{v\}\). \(D\subseteq V\) is a _dominating set_ (or a _perfect code_, respectively) of \(G\) if each vertex \(v\) finds a (unique) vertex \(u\) in \(D\cap N_{G}[v]\). A function \(f:V\to\{0,1,2\}\) is called a _Roman dominating function_ (Rdf for short) if each \(v\in V\) with \(f(v)=0\) is adjacent to a \(u\in V\) with \(f(u)=2\). The weight of a function \(f:V\to\{0,1,2\}\) is defined by \(\omega(f)=\sum_{v\in V}f(v)\). The decision problem Roman Domination has as input a graph \(G\) and a positive number \(k\), and the question is whether there exists a Roman dominating function such that the weight of the function is at most \(k\). Roman Domination is a well-studied variation of the dominating set. It is motivated by a defense strategy of the Roman Empire. The idea is to position the armies in regions in such a way that either (1) one army is in this region or (2) two armies are in one neighbored region. We model the distribution of the armies on the region (viewed as vertices of the graph) by a function that maps each region to the number of armies placed on this region. In recent years, this problem received notable attention [1; 2; 3; 4; 5; 6; 7]. As for the dominating set, there are also many variants of Roman Dominating Functions considered in the literature. Examples are Roman-\(\{2\}\)-domination (also known as Italian domination) [8] or double Roman Domination [9; 10; 11]. Clearly, as testified by books written on this topic [12; 13; 14], there are even more variations of the basic concept of domination in graphs. Here, we will consider two further variations of Roman Domination, perfect and Unique Response Roman Domination. A _perfect Roman dominating function_ (pRdf for short) (introduced by [PERSON] et al. [15]) is a Roman Dominating Function where each vertex with value \(0\) has _exactly_ one neighbor with value \(2\). If, moreover, all vertices with at least \(1\) as a value have no neighbor with value \(2\), then we have a _unique response Roman dominating function_ (urRdf for short) (as introduced in [16]). Both variations can be seen as a way to translate the idea of perfect code into the realm of Roman dominating function. A further motivation can also be the idea of positioning armies in regions: if the armies are placed according to a perfect Roman dominating function and a region without any army is attacked, then it is clear from which region an army moves to secure the attacked region, so no time is wasted to first agree on who is the one to take action and move to the endangered region. This article is a revised and expanded version of a paper entitled \"Perfect Roman Domination: Aspects of Enumeration and Parameterization\", which was presented at the 35 th International Workshop Combinatorial Algorithms, IWOCA 2024, which took place on the island of Ischia, Italy, 1-3 July 2024. An extended abstract of this paper has appeared in the proceedings of IWOCA 2024; see [17]. More formally, the decision problems sketched so far are given as follows:  
**Problem name:** Unique Response Roman Domination (URRD)  
**Given:** A graph \(G=(V,E)\) and \(k\in\mathbb{N}\)  
**Question:** Is there a unique response Roman dominating function \(f\) on \(G\) with \(\omega(f)\leq k\)?