# Perfect Roman Domination: Aspects of Enumeration and Parameterization +
## 3 Complexity and Enumeration in Special Graph Classes
### Interval Graphs  
We first start with a polynomial-time algorithm for Perfect Roman Domination for interval graphs. A graph \(G=(V,E)\) is called an _interval graph_ (see [30]) if, for \(v\in V\), there is an interval \(I_{v}=[l_{v},r_{v}]\) such that \(\{v,u\}\in E\) if and only if \(I_{v}\cap I_{u}\
eq\emptyset\). We can assume that the interval representation obeys \(\forall u,v\in V:r_{u}=r_{v}\implies u=v\). Theorem 3.1: Perfect Roman Domination _is polynomial-time solvable on interval graphs._  
Proof: Let \(G=(V,E)\) be an interval graph such that \(I_{v}=[l_{v},r_{v}]\) is the interval representation of \(v\in V\). The dynamic programming works from \"left to right\" according to some linear extension of the partial order defined as \(w\leq v\) if and only if \(l_{w}\leq l_{v}\wedge r_{w}\leq r_{v}\). For \(v\in V\), \(L_{v}\coloneqq\{w\in V\mid l_{w}\leq r_{v}\}\) denotes the set of vertices which are dominated by \(v\) or \"to the left\" of \(I_{v}\). To simplify our notation, we define \(P_{v}\coloneqq\{w\in V\setminus\{v\}\mid w\leq v\}\) to easily refer to the already considered vertices in the dynamic program. \(W_{v}\coloneqq\{w\in V\mid r_{v}<r_{w}\}\) is the set of not yet considered vertices. For \(v\in V\), \(u\in P_{v}\) and \(w\in P_{u}\), define \(Z_{u,v}\coloneqq(L_{v}\setminus(N[u]\cup N[v]))\cup(N(u)\cap N(v))\) and  
Figure 2: Counter-example of Remark 3. \(Y_{w,u,v}:=((N(u)\cap N(v))\setminus N[w])\cup(L_{v}\setminus(L_{u}\cup N[v]))\); see Figure 3. All these sets and their cardinalities can be computed before the actual dynamic programming starts. Also, we can compute the perfect Roman dominating functions that set at most one vertex to 2 and store their minimum weight in \(\min_{\leq 1}\). We need some more notation to formulate the dynamic programming algorithm and prove its correctness. For \(v\in V\) and \(u\in P_{v}\), define \(\Gamma_{u,v}:=\{f\in\{0,1,2\}^{V}\mid f|_{L_{v}}\in\mathcal{PRDF}(G[L_{v}]) \wedge f(u)=f(v)=2\wedge\forall w\in W_{u}\setminus\{v\}:f(w)\
eq 2\}\) and \(\gamma_{u,v}=\min_{f\in\Gamma_{u,v}}\omega(f)\). In the following, \(f^{\prime}_{u,v}\) will denote one function from \(\Gamma_{u,v}\) that attains this minimum, i.e., \(\omega(f^{\prime}_{u,v})=\gamma_{u,v}\). For the inductive computation, we will reuse the values \(\gamma_{w,u}\) with \(w\in P_{u}\). For the correctness of this approach, the following observations are helpful. 1. \(Z_{u,v}\) is connected to the function \(f_{u,v}\in\Gamma_{u,v}\) by setting \(V_{2}(f_{u,v})=\{u,v\}\) and \(V_{1}(f_{u,v})=Z_{u,v}\). 2. \(Y_{w,u,v}=V_{1}(f_{w,u,v})\setminus V_{1}(f^{\prime}_{u,u})\), where \(f_{w,u,v}\) is the auxiliary perfect Roman dominating function which we will construct from \(f^{\prime}_{w,u}\) in the induction step. 3. If \(f\in\Gamma_{u,v}\), then \(\tilde{f}:=f+X_{V\setminus L_{v}}\) is a perfect Roman dominating function on \(G\). If \(f\) is a minimum, then \(\tilde{f}\) is a minimum perfect Roman dominating function on \(G\). By the third property, after the inductive computations, \[\min\{\min_{\leq 1},\min\{\gamma_{u,v}+|V\setminus L_{v}|\mid v\in V,u\in P_{v} \}\}\] gives the minimum weight of any perfect Roman dominating function for \(G\). Assume now that \(v\) is a vertex for which we want to compute all relevant \(\gamma_{u,v}\) next, with \(u\in P_{v}\). The following claim contains a formula that describes how to do this. It implicitly also covers the initial step: then, \(\gamma_{u,v}=4+|Z_{u,v}|\) since \(P_{u}=\emptyset\). **Claim 2**. : _Let \(v\in V\) and \(u\in P_{v}\). Then,_  
\[\gamma_{u,v}=\min\{4+|Z_{u,v}|,2-|\{v\}\cap N(u)\cap N(w)|+\gamma_{w,u}+|Y_{ w,u,v}|\mid w\in P_{u}\}.\]  
Proof. : Let \(f^{\prime}_{w,u}\in\Gamma_{w,u}\) for \(w\in P_{u}\) such that \(\omega(f^{\prime}_{w,u})=\gamma_{w,u}\).