11institutetext:  Universität Trier, Fachbereich 4 – Abteilung
Informatikwissenschaften
54286 Trier, Germany.
11email<EMAIL_ADDRESS>
# Perfect Roman Domination and Unique Response Roman Domination

Henning Fernau  0000-0002-4444-3220 Kevin Mann  0000-0002-0880-2513

###### Abstract

The idea of enumeration algorithms with polynomial delay is to polynomially
bound the running time between any two subsequent solutions output by the
enumeration algorithm. While it is open for more than four decades if all
minimal dominating sets of a graph can be enumerated in output-polynomial
time, it has recently been proven that pointwise-minimal Roman dominating
functions can be enumerated even with polynomial delay. The idea of the
enumeration algorithm was to use polynomial-time solvable extension problems.

We use this as a motivation to prove that also two variants of Roman
dominating functions studied in the literature, named perfect and unique
response, can be enumerated with polynomial delay. This is interesting since
Extension Perfect Roman Domination is $\textsf{W}[1]$-complete if
parameterized by the weight of the given function and even
$\textsf{W}[2]$-complete if parameterized by the number vertices assigned 0 in
the pre-solution, as we prove. Otherwise, efficient solvability of extension
problems and enumerability with polynomial delay tend to go hand-in-hand. We
achieve our enumeration result by constructing a bijection to Roman dominating
functions, where the corresponding extension problem is polynomimal-time
solvable. Furthermore, we show that Unique Response Roman Domination is
solvable in polynomial time on split graphs, while Perfect Roman Domination is
NP-complete on this graph class, which proves that both variations, albeit
coming with a very similar definition, do differ in some complexity aspects.
This way, we also solve an open problem from the literature.

##  1 Introduction

###  1.1 Roman Domination

Historically, Roman Domination is motivated by the defense strategy of the
Roman Empire. The idea was to position the armies on regions in such a way
that either (1) there is one army in this region or (2) there are two armies
on one neighbored region. Translated to graphs we map each vertex to 0, 1 or
2. Such a function is called a Roman dominating function if each vertex with
value 0 has a neighbor of value 2. Roman Domination has as input a graph $G$
and a positive number $k$, and the question is if there exists a Roman
dominating function such that the sum of the values of all vertices is at most
$k$. In the last decades, this problem received notable attention [10, 14, 18,
20, 28, 29, 30, 33, 34, 37].

As for dominating set, there are also many variants of Roman dominating
functions which were considered in the literature. Examples are
Roman-$\\{2\\}$-domination (also know as Italian domination) [16], double
Roman domination [1, 7, 9] and total Roman domination [2].

###  1.2 Perfect Variations

Here, we will consider two further variations of Roman domination, perfect and
unique response Roman domination. A _perfect Roman dominating function_
(introduced by Henning _et al._ [24]) is a Roman dominating function where
each vertex with value 0 has _exactly_ one neighbor with value 2. If such a
function additionally satisfies that all vertices with at least 1 as value
have no neighbor with value 2, then it is a _unique response Roman dominating
function_ (introduced by Rubalcaba and Slater [35]). Both variations can be
seen as a way to translate the idea of perfect domination into the realm of
Roman dominating functions. As a further motivation, we can also consider the
idea of positioning armies on 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.

Supplementing results from the literature, we study the underlying
minimization problems on split and on cobipartite graphs, which shows that
these two seemingly very similar notions give raise to a different complexity
behavior. However, the main focus of this paper is on enumeration, both from
an input-sensitive and from an output-sensitive perspective.

###  1.3 Enumeration

Enumeration is wide area of research, as also testified by specialized
workshops like [21]. For some examples, we refer to the survey [40]. From a
practical point of view, enumeration can be interesting if not all aspects of
the problem have been satisfyingly modeled. For instance, it is possible to
enumerate all (inclusion-wise) minimal dominating sets of a graph of order $n$
in time $\mathcal{O}(1.7159^{n})$ [23]. As here only the size of the input
graph is taken into consideration, one also speaks of an input-sensitive
analysis. In contrast to classical complexity, one can often also give lower-
bound examples, which are families of graphs that possess, when taking an
$n$-vertex representative thereof, $\Omega(1.5704^{n})$ many minimal
dominating sets [23]. When lower and upper bounds match, we can consider this
type of enumeration as being optimal. However, even such an optimal
enumeration algorithm can be dissatisfying for a user, as she might have to
wait exponential time between two output solutions. This motivates to study
enumeration algorithms from an output-sensitive perspective. The most
important notions have been introduced by D. S. Johnson _et al._ [25]. We
focus on the most restricted variant. 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 is a very desirable property if two processes work as in a
production line: one process generates the solutions, while the other one
works on the generated solution. After finishing its work on one solution, the
second process does not want to work for a long time to start working on the
next solution. It is open since decades if all minimal dominating sets can be
enumerated with polynomial delay.

We motivate the enumeration of perfect/unique response Roman dominating
functions by the main result of F. N. Abu-Khzam _et al._ [3]. There, it is
proven that all minimal Roman dominating functions of a graph of order $n$ can
be enumerated in time $\mathcal{O}(1.9332^{n})$ with polynomial delay. In this
case, minimality is defined with respect to a pointwise order, _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$. To ensure polynomial delay for enumerating minimal Roman dominating
functions, F. N. Abu-Khzam _et al._ used polynomial-time solvable extension
problems.

###  1.4 Extension Problems

For a general definition of extension problems, we refer to [12]. Here, we
will only discuss the extension version of minimization problems on graphs.
Therefore, we can be more specific. Depending on the concrete problem (we
choose to illustrate this in the following with the classical problem
Dominating Set in parentheses), a graph $G=(V,E)$ defines the search space
$\textsf{presol}(G)$ of _pre-solutions_ (in our example,
$\textsf{presol}(G)=2^{V(G)}$) and a set of _solutions_
$\textsf{sol}(G)\subseteq\textsf{presol}(G)$ (dominating sets). For the
extension version, we also need to define a partial order $\preceq$ on
$\textsf{presol}(G)$ (which is $\subseteq$ for domination). The notion of a
_minimal solution_ is understood with respect to $\preceq$:
$s\in\textsf{sol}(G)$ is called minimal if, for each
$p\in\textsf{presol}(G)\setminus\\{s\\}$, $p\preceq s$ implies
$p\notin\textsf{sol}(G)$. An instance of the extension version consists, apart
from the graph $G$, in a pre-solution $p\in\textsf{presol}(G)$ (some set of
vertices in our example). The question is if there exists a minimal solution
$s\in\textsf{sol}(G)$ with $p\preceq s$. Notice that a typical branching
algorithm used for the enumeration of all minimal solutions will implicitly
create a pre-solution $p$, and then efficiently determining if any minimal
solution exists that extends $p$ would be very beneficial. In the special case
of Extension Roman Domination, $\textsf{presol}(G)$ is the set of all mappings
$f:V\to\\{0,1,2\\}$ and $\textsf{sol}(G)$ is the set of all Roman dominating
functions. Now, $\preceq$ is given by the partial order $\leq$ described
above: $f\leq g$ holds if $f(v)\leq g(v)$ for each $v\in V$.

###  1.5 Organization of the Paper

We start by introducing important notations and definitions in section 2. Then
we consider the optimization problems Perfect Roman Domination and Unique
Response Roman Domination on split and cobipartite graphs. We show that
Perfect Roman Domination is NP-complete while Unique Response Roman Domination
is polynomial-time solvable. To our knowledge, this is the first graph class
where this is shown. Section 4 provides a polynomial-delay enumeration
algorithm for unique response Roman dominating functions. In section 5 we
demonstrate that Extension Perfect Roman Domination is NP-complete,
$\textsf{W}[1]$-complete when parameterized by the pre-solution size and
$\textsf{W}[2]$-complete when parameterized by the number of vertices assigned
0 by the pre-solution. Nonetheless, we present a way to enumerate all minimal
perfect Roman dominating functions with polynomial delay in section 6 by
showing a one-to-one correspondence between minimal perfect Roman dominating
functions and minimal Roman dominating functions.

##  2 Preliminaries

###  2.1 General Notions

Let $\mathbb{N}$ denote the set of all nonnegative integers (including 0). For
$n\in\mathbb{N}$, we will use the notation $[n]\coloneqq\\{1,\ldots,n\\}$. Let
$G=(V,E)$ be a graph. $N_{G}(v)$ 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\\}$. For a set $A\subseteq
V$ the open neighborhood is defined as $N_{G}(A)\coloneqq\left(\bigcup_{v\in
A}N_{G}(v)\right)$. The closed neighborhood of $A$ is given by
$N_{G}[A]\coloneqq N_{G}(A)\cup A$. Furthermore, the private neighborhood of a
vertex $v\in A$ with respect to $G$ and $A$ is denoted by $P_{G,A}(v)\coloneqq
N_{G}[v]\setminus N_{G}[A\setminus\\{v\\}]$.

Let $G=(V,E)$ be a graph. We say $D\subseteq V$ is a dominating set if
$N[D]=D$. A set $D\subseteq V$ is called _perfect dominating_ if $D$ is a
dominating set and for all $v,u\in D$ with $v\neq u$, $N[v]\cap
N[u]=\emptyset$.

Let $A,B$ be two sets. $B^{A}$ is the set of all function $f:A\to B$. For a
functions $f:A\rightarrow\mathbb{N}$ on a finite set $A$, we define
$\omega(f)=\sum_{a\in A}f(a)$. For $A\subseteq B$ $\chi_{A}:B\to\mathbb{N}$
denotes the characteristic function ($\chi(a)=1$ if and only if $a\in A$;
$\chi(a)=0$ otherwise)

###  2.2 Basic Decision Problems

Problem name: Unique Response Roman Domination
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$?

Problem name: Perfect Roman Domination
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 even on regular bipartite
graphs [11]. Furthermore, Banerjee _et al._ [6] showed that this problem is
NP-complete on chordal graphs, and polynomial-time solvable on distance-
hereditary and interval graphs. They also prove that there is no Unique
Response Roman Domination polynomial-time approximation algorithm within a
factor of $n^{1-\epsilon}$ for any constant $\epsilon>0$ and any input graph
of order $n$, unless $\textsf{NP}=\textsf{P}$.

  * •

Perfect Roman Domination is NP-complete on chordal graphs, planar graphs, and
bipartite graphs and polynomial time solveable on block graphs, cographs,
series-parallel graphs, and proper interval graphs [8].

###  2.3 Characterizing Perfect Roman Dominating Functions

Consider a graph $G=(V,E)$ and a function $f:V\rightarrow\\{0,1,2\\}$. We
define $V_{i}(f):=\\{v\in V\mid f(v)=i\\}$ for each $i\in\\{0,1,2\\}$. If
$v\in V$ obeys $f(v)=2$, then $u\in N_{G}(v)$ with $f(u)=0$ is called a
_private neighbor_ of $v$ (with respect to $f$) if $|N_{G}(u)\cap
V_{2}(f)|=1$.

###### Observation 1

Let $G=(V,E)$ be a graph and $f:V\rightarrow\\{0,1,2\\}$.

  1. 1.

If $f$ is a perfect Roman dominating function, then every neighbor $u$ with
$f(u)=0$ of some $v$ with $f(v)=2$ is a private neighbor of $v$.

  2. 2.

If $f$ is a Roman dominating function such that every neighbor $u$ with
$f(u)=0$ of some $v$ with $f(v)=2$ is a private neighbor of $v$, then $f$ is a
perfect Roman dominating function.

###### Proof

Let us first prove the first item. If it were not true, then there would be
some neighbor $u$ with $f(u)=0$ of some $v$ with $f(v)=2$ that is non-private,
_i.e._ , there exists some $v^{\prime}\in N_{G}(u)$, $v^{\prime}\neq v$, with
$f(v^{\prime})=2$. This contradicts the assumption that $f$ is a perfect Roman
dominating function. To see the second implication, observe that if $f$ is a
Roman domination function that is not perfect, then there must be a vertex $u$
with $f(u)=0$ such that $u$ has two neighbors $v_{1},v_{2}$ with
$f(v_{1})=f(v_{2})=2$. Hence, $u$ is not a private neighbor of $v_{1}$. ∎

##  3 Optimization on Split and Cobipartite Graphs

A split graph $G=(V,E)$ is a graph such that the vertex set $V$ can be
partitioned into $C,I$, where $C$ is a clique and $I$ is an independent set of
$G$. It seems to be open in which complexity class Perfect Roman Domination
and Unique Response Roman Domination are on split graphs, as explicitly asked
in [6]. The main result of this section will give the answers.

###  3.1 Unique Response Roman Domination on Split Graphs

###### Lemma 1

Let $G=(V,E)$ be a connected split graph with a clique $C$ and an independent
set $I$ such that $V=C\cup I$ and $C\cap I=\emptyset$. For each unique
response Roman dominating function $f:V\rightarrow\\{0,1,2\\}$, one of the
following conditions holds:

  * •

$V_{2}(f)\cap I=\emptyset$ and $|V_{2}(f)\cap C|\leq 1$; or

  * •

$V_{2}(f)\subseteq I$.

###### Proof

Suppose that $V_{2}(f)$ is not a subset of $I$. By the definition of unique
response Roman dominating function, two vertices of $C$ cannot have the value
2, since $C$ is a clique. Hence, $|V_{2}(f)\cap C|\leq 1$. For the sake of
contradiction, assume there are $v\in I$ and $u\in C$ with $f(u)=f(v)=2$. As
$f$ is a unique response Roman dominating function, $u$ and $v$ cannot be
neighbors. Since $\emptyset\subsetneq N_{G}(v)\subseteq C$ holds as $G$ is
connected, $v$ has a neighbor $w\in C$. This contradicts the assumption on
$f$, as $|N_{G}(w)\cap V_{2}(f)|\geq 2$. ∎

Let us take a look at the unique response Roman dominating function for the
two cases of 1. Without loss of generality, we can assume that for the given
split graph $G=(V,E)$, we have a decomposition $V=C\cup I$ into a clique $C$
and an independent set $I$ such that $C$ is inclusion-wise maximal. Consider
the unique response Roman dominating function $f:V\rightarrow\\{0,1,2\\}$.

First assume $f$ fulfills $V_{2}(f)\cap I=\emptyset$ and $|V_{2}(f)\cap C|\leq
1$. Since $V_{2}(f)\cap C=\emptyset$ would imply $f=1$ (constant) and
$\omega(f)=|C|+|I|$, let us assume $\\{v\\}=V_{2}(f)\cap C$. Therefore, $C\cap
V_{1}(f)=\emptyset$ holds. Hence, $\omega(f)=2+|I\setminus N_{G}(v)|$. This
implies $u_{R}(G)\leq\min_{v\in C}\left(2+|I\setminus N_{G}(v)|\right)\leq
2+|I|$.

Secondly, let us assume $V_{2}(f)\subseteq I$. As $I$ is an independent set
and there is no vertex in $C$ with the value 2, $f(v)\geq 1$ for each $v\in
I$. This implies

$\omega(f)=|I|+|V_{2}(f)|+|C\setminus N_{G}(V_{2}(f))|\geq|I|+1.$

Equality holds if and only if there exists a vertex $v\in I$ with $N_{G}(v)=C$
and, for all $u\in I$, $f(u)=2\iff u=v$. In this case $C$ is not maximal,
contradicting our assumption. Thus, this second case can never give a smaller
value than the first one, _i.e._ , $u_{R}(G)\leq\min_{v\in
C}\left(2+|I\setminus N_{G}(v)|\right)$. In order to solve Unique Response
Roman Domination on $G$, we only have to find the vertex with the highest
degree, as it will be in a maximal clique.

###### Corollary 1

Unique Response Roman Domination can be solved in time $\mathcal{O}(n+m)$ on
split graphs.

###  3.2 Perfect Roman Domination on Split Graphs

Interestingly, the seemingly very similar problem Perfect Roman Dominationon
split graphs is harder to solve. To see this, we will use a problem called
Perfect Domination that is defined next.

Problem name: Perfect Domination
Given:  A graph $G=(V,E)$ and $k\in\mathbb{N}$ Question:  Is there a perfect
dominating set $D$ on $G$ with $|D|\leq k$?

It is known that Perfect Roman Dominationis NP-complete, see [19].

###### Theorem 3.1

Perfect Roman Domination on split graphs is NP-complete.

###### Proof

Membership follows from Perfect Roman Domination on general graphs. To prove
NP-hardness, we will use Perfect Domination. Let $G=(V,E)$ be a graph and
$k\in\mathbb{N}$. To avoid trivialities, $k\leq|V|$.

Define $t=3\cdot|V|+4$, $k^{\prime}=k+|V|+4$ and
$G^{\prime}=(V^{\prime},E^{\prime})$ with

$\begin{split}V^{\prime}=&\\{x,y\\}\cup\\{v^{\prime},v_{i}\mid v\in
V,i\in[t]\\}\cup\\{a_{1},b_{1},\ldots,a_{t},b_{t}\\},\\\
E^{\prime}=&\\{\\{x,a_{i}\\},\\{y,b_{i}\\}\mid
i\in\left[t\right]\\}\cup\\{\\{v^{\prime},u_{i}\\}\mid v,u\in V,u\in
N[v],i\in[t]\\}\cup\\\ &\binom{\\{x,y\\}\cup\\{v^{\prime}\mid v\in
V\\}}{2}.\end{split}$

The instance $(G^{\prime},k^{\prime})$ of Perfect Roman Domination can be
constructed in polynomial time. Moreover, $G^{\prime}$ is easily seen to be a
split graph. We still have to prove that $(G,k)$ is a yes-instance of Perfect
Domination if and only if $(G^{\prime},k^{\prime})$ is a yes-instance of
Perfect Roman Domination.

Let $S\subseteq V$ be a perfect dominating set of $G$ with $|S|\leq k$. Define
$f\in\\{0,1,2\\}^{V}$ by the sets

$\begin{split}V_{0}(f)=&\\{v_{i}\mid i\in[t],v\in V\\}\cup\\{a_{i},b_{i}\mid
i\in[t]\\},\\\ V_{1}(f)=&\\{v^{\prime}\mid v\notin S\\},\\\
V_{2}(f)=&\\{x,y\\}\cup\\{v^{\prime}\mid v\in S\\}.\end{split}$

This implies $\omega(f)=|V\setminus S|+4+2\cdot|S|=|V|+4+|S|\leq k^{\prime}.$
The set $\\{a_{1},\ldots,a_{t}\\}\cup\\{v^{\prime}\mid f(v)\neq 2\\}$ is only
dominated by $x$ and the vertices $b_{1},\ldots,b_{t}$ are only dominated by
$y$. Assume there is a $v\in V$ and $i\in[t]$ such that
$|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|\neq 1$. By
$N_{G^{\prime}}(v_{i})=\\{u^{\prime}\mid u\in N_{G}[v]\\}$, this implies
$|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|=|N_{G}(v)\cap S|\neq 1$. This
contradicts that $S$ is a perfect dominating set.

Assume that $f\in\\{0,1,2\\}^{V^{\prime}}$ is a minimum perfect Roman
dominating function with $\omega(f)\leq k^{\prime}$.

###### Claim

For each $z\in\\{v_{i},a_{i},b_{i}\mid i\in[t],v\in V\\}$, it holds that
$f(z)=0$.

_Proof._ For the sake of contradiction, assume that there is some $v\in V$ and
$i\in[t]$ with $f(v_{i})=2$. If $v_{i}$ would not have a private neighbor
$u^{\prime}$ with $f$-value 0, then $f^{\prime}=f-\chi_{\\{v_{i}\\}}$ would be
a smaller perfect Roman dominating function. This contradicts the minimality
of $f$. This implies $\\{x,y\\}\cup\\{z^{\prime}\mid z\in V\\}\subseteq
N_{G^{\prime}}(u^{\prime})$ has no vertex with $f$-value 2. Thus,
$N_{G^{\prime}}(v_{i})\cap V_{2}(f)=\emptyset$. Therefore, $f(v_{j})\neq 0$
for each $j\in[t]$. Hence $\omega(f)\geq t+1>k^{\prime}$, contradicting the
choice of $f$.

Assume there is some $v\in V$ and $i\in[t]$ with $f(v_{i})=1$. Furthermore, we
can assume $|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|\neq 1$, as otherwise,
$f-\chi_{\\{v_{i}\\}}$ would be a smaller perfect Roman dominating function.
As by construction $N_{G^{\prime}}(v_{i})=N_{G^{\prime}}(v_{j})$ for each
$j\in[t]$, we find $|N_{G^{\prime}}(v_{i})\cap
V_{2}(f)|=|N_{G^{\prime}}(v_{j})\cap V_{2}(f)|$. If
$|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|=0$, then $f(v_{j})\neq 0$ holds for each
$j\in[t]$, since $v_{j}$ is not dominated. Hence, $\omega(f)\geq t\cdot|V|\geq
t>k^{\prime}$, contradicting the choice of $f$. Assume
$|N_{G^{\prime}}(v_{i})\cap V_{2}(f)|\geq 2$. Thus, for each $j\in[t]$,
$f(v_{j})\neq 0$, as otherwise, $f$ is not perfect. This contradicts the
construction as above.

We can discuss the claims concerning $a_{i}$ and $b_{i}$ along very similar
lines. $\Diamond$

Further, we know $f(x)=f(y)=2$. Define $S=\\{v\mid f(v^{\prime})=2\\}$. As
$f(v_{i})=0$ for each $v\in V,i\in[t]$, $|N_{G^{\prime}}(v_{i})\cap
V_{2}(f)|=1$. This implies that $|N_{G}[v]\cap S|=1$ for each $v\in V$.
Therefore, $S$ is a perfect dominating set.

Since $f(x)=f(y)=2$, $f(v^{\prime})\geq 1$ for all $v\in V$. This implies that
$\omega(f)=|V|+|V_{2}(f)|+4=|V|+|S|+4\leq k^{\prime}$. Hence, $|S|\leq
k^{\prime}-4-|V|=k$. ∎

###### Theorem 3.2

$\omega\left(f\right)-\textsc{Perfect Roman Domination}$ can be solved in FPT
time on split graphs.

###### Proof

Let $G=(V,E)$ be a split graph with the vertex set partition $V=C\cup I$,
where $C$ is a clique and $I$ an independent set. Further, let
$f:V\to\\{0,1,2\\}$ be a minimum perfect Roman dominating function on $G$.
Then $V_{2}(f)\cap I=\emptyset$ or $V_{2}(f)\cap C=\emptyset$. For $v\in
V_{2}(f)\cap I$ and $c\in V_{2}(f)\cap C$, $f-\chi_{\\{v\\}}$ would be a
perfect Roman dominating function with
$\omega\left(f-\chi_{\\{v\\}}\right)\leq\omega\left(f\right)$.

For $V_{2}(f)\cap C=\emptyset$, we just branch on each vertex in $I$ if gets
the value $1$ or $2$. The vertices cannot get the value $0$ as they cannot be
dominated by a other vertex. After deciding this we can delete the vertex and
the parameter goes down by either $1$ or $2$. This gives us the branching
vector $(1,2)$. When we have branched on each vertex in $I$, then we assign
$0$ to each $c\in C$ with $|V_{2}(f)\cap N(c)|=1$ and $1$ otherwise (this is
important to get the perfect Roman dominating function property). Now, we only
need to check if $\omega\left(f\right)$ is smaller than the given parameter
value.

Now, we consider the perfect Roman dominating functions $f\in\\{0,1,2\\}^{V}$
with $V_{2}(f)\cap I=\emptyset$. As $C$ is a clique, if $|V_{2}(f)\cap C|\geq
2$, then $C\subseteq V_{1}(f)\cup V_{2}(f)$. First we consider the perfect
Roman dominating functions with $|V_{2}(f)\cap C|=1$. Since these functions
are unique response Roman dominating functions, this can be done in polynomial
time. After this, we guess two vertices from $C$ and assign the value $2$ to
these vertices. From now on, we can branch on the remaining vertices in $C$ if
these will be assigned to $1$ or $2$. Analogously to $V_{2}(f)\cap
C=\emptyset$, then we assign $0$ to each $v\in I$ with $|V_{2}(f)\cap N(v)|=1$
and $1$, otherwise. In this case, we also have to check if
$\omega\left(f\right)$ is smaller than the given parameter value.

Our algorithm runs in time $\mathcal{O}^{*}(\Phi^{k})$, where $\Phi$ is the
golden ratio and $k$ the parameter. ∎

###  3.3 Perfect Roman Domination on Cobipartite Graphs

For the remaining section, we consider cobipartite graphs, which are the
complementary graphs of bipartite graphs. These graphs can be also
characterized as graph for which the vertex set can be partitioned into two
cliques. On this graph class, Perfect Roman Domination is solvable polynomial-
time.

###### Theorem 3.3

Perfect Roman Domination is polynomial-time solvable on cobipartite graphs.

###### Proof

Let $G=(V,E)$ be a cobipartite graph with the partition into the two cliques
$C_{1},C_{2}\subseteq V$. For $v\in V$ define the perfect Roman dominating
function

$g_{v}:V\to\\{0,1,2\\},x\mapsto\begin{cases}0,&x\in N(v)\\\ 1,&x\in V\setminus
N[v]\\\ 2,&x=v.\end{cases}$

Let $f\in\\{0,1,2\\}^{V}$ be a perfect Roman dominating function with
$|V_{2}(f)\cap C_{1}|\geq 2$ and $v\in C_{2}$. For each $u\in C_{1}\setminus
V_{2}(f)$, $|V_{2}(f)\cap N(u)|\geq 2$. Hence $C_{1}\subseteq V_{1}(f)\cup
V_{2}(f)$. Since $C_{2}\subseteq N[v]=V_{0}(g_{v})\cup\\{v\\}$,
$\omega\left(g_{v}\right)\leq|C_{1}|+2\leq\omega\left(f\right)$.
Symmetrically, $\omega\left(g_{v}\right)\leq|C_{1}|+2\leq\omega\left(f\right)$
for $v\in C_{1}$ and a perfect Roman dominating function $f$ with
$|V_{2}(f)\cap C_{2}|\geq 2$. Let $f$ be a minimum perfect Roman dominating
function on $G$. We can assume $|V_{2}(f)\cap C_{i}|\leq 1$ for each
$i\in\\{1,2\\}$. This leaves only $|V|^{2}+|V|$ many possibilities. ∎

###  3.4 Relating to 2-Packings

As mentioned before, Cabrera _et al._ [11] proved that Unique Response Roman
Domination is NP-complete on bipartite graphs. For cobipartite graphs, this
problem is polynomial-time solvable. For this result, we use the idea of
2-packings. Let $G=(V,E)$ be a graph. A set $S\subseteq V$ is called
_2-packing_ if the distance between two vertices in $S$ is at least 3. Targhi
_et al._ [39] presented a proof for $u_{r}(G)=\min\\{2|S|+|V(G)\setminus
N_{G}[S]|\mid S\text{ is a 2-packing}\\}$. Analogously to this, we can prove
that, for each graph $G=(V,E)$, there exists a bijection $\psi_{G}$ between
all 2-packings of the graph and all unique response Roman dominating
functions. Here, for a 2-packing $S$ and for $x\in V$,

$\psi_{G}(S)(x)=\begin{cases}0,&x\in N(S)\setminus S\\\ 1,&x\in V\setminus
N(S)\\\ 2,&x\in S.\end{cases}$

This also yields that, for each unique response Roman dominating function $f$,
$V_{2}(f)$ is a 2-packing. This is the main idea of our algorithm.

###### Lemma 2

Unique Response Roman Domination is polynomial-time solvable on cobipartite
graphs. Furthermore, there are at most $\frac{|V|^{2}}{4}$ many 2-packings, or
unique response Roman dominating functions, on $G=(V,E)$.

###### Proof

Let $G=(V,E)$ be a cobipartite graph, together with the partition into the two
cliques $C_{1},C_{2}\subseteq V$. Clearly, two vertices from the same clique
cannot be in a 2-packing at the same time. Therefore, from each clique, there
can be at most one vertex in the 2-packing. This implies that there are at
most $|C_{1}|\cdot|C_{2}|$ many 2-packings, or unique response Roman
dominating functions. As $C_{1},C_{2}$ is a partition of $V$, this leads to
$|C_{1}|\cdot|C_{2}|=|C_{1}|\cdot|V\setminus
C_{1}|=|C_{1}|\cdot\left(|V|-|C_{1}|\right)$ many 2-packings. This expression
is maximal if $|C_{1}|=|C_{2}|$, which implies that there are at most
$\frac{|V|^{2}}{4}$ many 2-packings or unique response Roman dominating
functions on $G$. ∎

The bound $\frac{|V|^{2}}{4}$ is tight: we get the number for the complement
of a complete bipartite graph $K_{t,t}$ where both classes have the same size
$t$. This is interesting as there could be exponentially many unique response
Roman dominating functions even on connected split graphs, which is quite a
related class of graphs. To this end, we only need to consider the split graph
$G=(V,E)$ with $V\coloneqq C\cup I$, $C\coloneqq\\{c_{1},\ldots,c_{t}\\}$,
$I\coloneqq\\{v_{1},\ldots,v_{2t}\\}$ and

$E\coloneqq\binom{C}{2}\cup\\{\\{c_{i},v_{2i-1}\\},\\{c_{i},v_{2i}\\}\mid
i\in\\{1,\ldots,t\\}\\}.$

Clearly, $|V|=3t$. By the arguments from 1, we know that for each unique
response Roman dominating function $f$ with $|V_{2}(f)\cap C|=1$,
$|V_{2}(f)|=1$. There are $t$ many such unique response Roman dominating
functions. Let $f$ be a unique response Roman dominating function with
$V_{2}(f)\cap C=\emptyset$. In this situation, for each
$i\in\\{1,\ldots,t\\}$, there three ways to dominate $c_{i}$:

  * •

$f(c_{i})=f(v_{2i-1})=f(v_{2i})=1$,

  * •

$f(c_{i})=f(v_{2i})=0$ and $f(v_{2i-1})=2$,

  * •

$f(c_{i})=f(v_{2i-1})=0$ and $f(v_{2i})=2$.

This implies that there are $t+3^{t}=\frac{|V|}{3}+\sqrt[3]{3}^{|V|}$ many
unique response Roman dominating function. $\Omega(\sqrt[3]{3}^{|V|})$ is even
a tight bound for connected split graphs. This is the case as each unique
response Roman dominating function on a graph without isolated vertices is a
minimal Roman dominating function. Therefore, we could use the enumeration
algorithm for minimal Roman dominating functions on split graph from [5] which
runs in $\mathcal{O}(\sqrt[3]{3}^{|V|})$.

###### Remark 1

It should be mentioned that the polynomial delay property of this algorithm is
not inherited for enumerating unique response Roman dominating function, as
not each minimal Roman dominating function is a unique response Roman
dominating function. Nonetheless, we will present a sketch of a polynomial-
delay branching enumeration algorithm. For this purpose, we consider each
2-packing on a connected split graph and use the bijection between unique
response Roman dominating functions and 2-packings. The measure is for each
vertex the same.

Let $G=(V,E)$ be a connected split graph with the partion $V=C\cup I$ where
$C$ is a clique and $I$ is an independent set. With the arguments from above,
we can first enumerate each of the $|C|$ many 2-packings $S$ with $S\cap
C\neq\emptyset$. From now on, we branch on the vertices in $I$ if they will be
in $S$ or not. If the vertex from $I$ is not in $S$, then we delete this
vertex. If we put a vertex from $v$ into $S$, then we delete, for each $u\in
N(v)$, the whole set $\\{u\\}\cup\left(N(u)\cap I\right)$. Furthermore, we
delete vertices from $C$ which have no neighbors in $I$. We branch on the
vertex $v\in I$ with the highest degree. If $\deg(v)\geq 3$, then by putting
the vertex in $S$ we delete 4 vertices. This leads to a branching vector
$(4,1)$ (the branching value is below 1.3804). For $\deg(v)=2$, we have to
make a case distinction in the analysis: If $v$ is the only neighbor in $I$
for each of the neighbors of $v$, then in both cases these vertices will be
deleted after this branch. This implies the branching vector $(3,3)$ (The
branching value is $\sqrt[3]{2}<\sqrt[3]{3}$). Otherwise, at least 4 vertices
will be deleted after putting $v$ into $S$. This would again lead to the
branching vector $(4,1)$.

Therefore, we can assume that each vertex in $I$ has exactly one neighbor. Let
$c$ be this neighbor. If $|N(c)\cap I|\geq 3$, after putting $v$ into $S$, we
would delete at least 4 vertices and the branching would be again $(4,1)$. For
$N(c)\cap=\\{v\\}$, we would delete $c$ in each case. This leads to the
branching vector $(2,2)$ (the branching value is $\sqrt{2}\leq\sqrt[3]{3}$).
The remaining case is $|N(c)\cap I|=2$. This is considered in the
$\Omega(\sqrt[3]{3}^{|V|})$ example above. This implies the claimed running
time of $\mathcal{O}^{*}({\sqrt[3]{3}\,}^{n})$.

This algorithm is a modification of the recursive backtracking algorithm of
[31] and is polynomial delay with the same arguments. The algorithm of [31] is
a general approach to enumerate all sets of $\mathcal{F}\subseteq 2^{U}$ for a
universe $U$, where $\mathcal{F}$ fulfills the downward closure property: if
$X\in\mathcal{F}$ and $Y\subseteq X$, then $Y\in\mathcal{F}$.

###### Corollary 2

There exists an algorithm which enumerates all unique response Roman
dominating functions of a connected split graph of order $n$ in time
$\mathcal{O}^{*}(\sqrt[3]{3}^{n})$ with polynomial delay. Furthermore, there
are connected split graphs of order $n$ that have at least
$\Omega({\sqrt[3]{3}\,}^{n})$ many unique response Roman dominating functions.

##  4 Enumerating All Unique Response Roman Dominating Functions

In this section, we will enumerate unique response Roman dominating functions
on graphs without isolated vertices. The reason for this restriction is that
there are two choices for a unique response Roman dominating function to
dominate an isolated vertex (either 1 or 2). This would result in $2^{n}$ many
unique response Roman dominating functions. In this case, an algorithm which
decides for each vertex if it assigns the value $2$ or not (at the end each
vertex $v$ without a value-2 vertex in its closed neighborhood will be
assigned 1, and it will be assigned 0, otherwise) would have perfect running
time. Furthermore, the value $2$ on an isolated vertex is no good idea, as in
the Unique Response Roman Domination problem, we try to minimize the value of
the function. In this case, each unique response Roman dominating function
that assigns a $2$ to an isolated vertex would give rise to a smaller unique
response Roman dominating function which dominates the remaining vertices in
the same way. Therefore, as we are going to enumerate all unique response
Roman dominating functions in this section, not only the minimal ones, we are
considering graphs without isolated vertices in the following.

Recall that Junosza-Szaniawski and and Rzążewski [26] provided an enumeration
algorithm for 2-packings on connected graphs of order $n$ which runs in time
$\mathcal{O}(1.5399^{n})$. Remember that there exists a bijection between all
2-packings and all unique response Roman dominating functions of a graph. Even
if this is an interesting algorithm for enumerating all unique response Roman
dominating functions on connected graphs, there are worse cases on graphs
without isolated vertices:

On $P_{2}=(\\{v,u\\},\\{\\{v,u\\}\\})$, there are the following three possible
unique response Roman dominating functions:
$2\cdot\chi_{\\{v\\}},2\cdot\chi_{\\{u\\}}$ and $\chi_{\\{v,u\\}}$.

###### Corollary 3

There are graphs of order $n$ without isolates that have at least
${\sqrt{3}\,}^{n}$ many minimal unique response Roman dominating function.

We will also need the next observation in the following.

The remaining section will be used to show the following theorem that
basically proves that the given simple example is optimal.

###### Theorem 4.1

There is a polynomial-space algorithm that enumerates all unique response
Roman dominating functions of a given graph (without isolated vertices) of
order $n$ with polynomial delay and in time
$\mathcal{O}^{*}({\sqrt{3}\,}^{n})$.

For the proof, we will construct a branching algorithm. To do this, we need
the sets $A,V_{0},V_{1},V_{2},\overline{V_{2}}$. In $V_{0},V_{1},V_{2}$, we
find the vertices with the respective values 0, 1, 2. Hence, $V_{2}$ has to be
a 2-packing. $\overline{V_{2}}$ contains the vertices which will not be $2$
but it is not clear if they are $0$ or $1$ ($\overline{V_{2}}\cap(V_{0}\cup
V_{1})=\emptyset$). $A$ contains vertices which are completely undecided so
far, which reflects the situation at the start of the algorithm. For the
analysis, we use the measure $\mu=|A|+\omega\cdot|\overline{V_{2}}|$. Notice
that at the very beginning, $V=A$, so that then $\mu=|V|$.

For the polynomial delay part of the proof, we will consider the search tree
representation of a run of a branching algorithm on a graph $G$. This is a
rooted tree where all edges are orientated away from the root. Each node
represents a quintuple $(A,\overline{V_{2}},V_{0},V_{1},V_{2})$ of pairwise
disjoint sets whose union is $V$. There is an edge from one node to another
one in this tree if the second node can be produced in one of the cases of the
next branching step. Reduction rules can be executed in polynomial time and we
hence stay within the same node of the search tree.

###### Reduction Rule 1

If there are $v,u\in V_{2}$, $u\neq v$, with $N_{G}[v]\cap
N_{G}[u]\neq\emptyset$, then skip this branch.

In other words, we have detected a leaf in the search tree in which no
solution is output. This reduction rule is sound as $V_{2}$ would not be a
2-packing anymore.

###### Reduction Rule 2

If there is a vertex $v\in A$ with $N_{G}(v)\cap(\overline{V_{2}}\cup
A)=\emptyset$, then put $v$ into $\overline{V_{2}}$.

###### Lemma 3

Reduction Rule 2 is sound.

###### Proof

Let $f$ be a unique response Roman dominating function on $G$ with
$V_{2}(f)\cap(V_{2}\cup\overline{V_{2}})=V_{2}$, $V_{0}\subseteq V_{0}(f)$ and
$V_{1}\subseteq V_{1}(f)$. Since we assigned 0 to a vertex only if it has a
neighbor in $V_{2}$ and $N_{G}(u)\cap V_{2}(f)$ is empty for each $u\in
V_{1}(f)\cup V_{2}(f)$, $v\in V_{2}(f)$ would contradict the properties of
unique response Roman dominating functions. ∎

###### Reduction Rule 3

If there is a vertex $v\in\overline{V_{2}}$ with $N_{G}[v]\cap A=\emptyset$,
then put $v$ into $V_{1}$.

###### Lemma 4

Reduction Rule 3 is sound.

###### Proof

Since $N_{G}[v]\cap V_{2}(f)$ will be empty for a unique response Roman
dominating function $f$ with $V_{2}\subseteq V_{2}(f)$ and
$\overline{V_{2}}\cap V_{2}(f)=\emptyset$, $f(v)$ must be 1. ∎

###### Branching Rule 1

Let $v\in A$ with $|N_{G}(v)\cap A|\geq 2$. Then branch as follows:

  1. 1.

Put $v$ in $V_{2}$ and all vertices of $N_{G}(v)$ in $V_{0}$.

  2. 2.

Put $v$ in $\overline{V_{2}}$.

###### Lemma 5

The branching is a complete case distinction. Moreover, it leads at least to
the following branching vector: $(3,1-\omega)\,.$

###### Proof

If a vertex is in $V_{2}$, then each neighbor has to be in $V_{0}$. Therefore,
this is a complete case distinction. In the first case, we put three vertices
from $A$ into $V_{2}$ or $V_{0}$. Hence, the measure decreases by $3$. The
last case is decreasing the measure by $1-\omega$, since we only move $v$ from
$A$ to $\overline{V_{2}}$. ∎

###### Branching Rule 2

Let $v\in A$ with $\\{u\\}=N_{G}(v)\cap A$ and $\\{v\\}=N_{G}(u)\cap A$. Then
branch as follows:

  1. 1.

Put $v$ in $V_{2}$ and $N_{G}(v)$ in $V_{0}$.

  2. 2.

Put $u$ in $V_{2}$ and $N_{G}(u)$ in $V_{0}$.

  3. 3.

Put $v,u$ in $V_{1}$.

###### Lemma 6

The branching is a complete case distinction. Moreover, it leads at least to
the following branching vector: $(2,2,2)\,.$

###### Proof

In this case $v$ and $u$ cannot be in $V_{2}$ at the same time. If
$v,u\in\overline{V_{2}}$, then these vertices cannot be dominated, as
$N_{G}(v)\cap(V_{2}\cup A)=N_{G}(u)\cap(V_{2}\cup A)=\emptyset$. Since the
values of $v,u$ are fixed after this branch, the measure decreases by (at
least) $2$ in each case. ∎

###### Branching Rule 3

Let $v\in A$ with $N_{G}(v)\subseteq\overline{V_{2}}$. Then branch as follows:

  1. 1.

Put $v$ in $V_{2}$ and all vertices of $N_{G}(v)$ in $V_{0}$.

  2. 2.

Put $v$ in $V_{1}$.

###### Lemma 7

The branching is a complete case distinction. Moreover, it leads at least to
the following branching vector: $(1+\omega,1)\,.$

###### Proof

Because of Reduction Rule 2, we know that $v$ has at least one neighbor in
$\overline{V_{2}}$. If $v$ is assigned to $2$, then its neighbors have to be
in $V_{0}$ (this decreases the measure by at least $1+\omega$).
$v\in\overline{V_{2}}$ triggers Reduction Rule 3, which implies $v\in V_{1}$.
This reduces the measure by $1$. ∎

######  Proof (Theorem 4.1)

First we will show that the algorithm covers each case. Branching Rule 1
implies that each vector in $A$ has at most one neighbor in $A$. By Branching
Rule 2, there is no edge between two vertices in $A$. If there is a vertex in
$A$ with a neighbor in $\overline{V_{2}}$, then this triggers Branching Rule
3. For the remaining vertices in $A$, we use Reduction Rule 2. If a vertex in
$\overline{V_{2}}$ has no neighbor in $A$, we use Reduction Rule 3. Hence, the
branching algorithm handles each case for $V\nsubseteq V_{0}\cup V_{1}\cup
V_{2}$. As each branching is complete the branching algorithm returns all
unique response Roman dominating functions of $G$. The running time of the
algorithm follows by Table 1.

By an inductive argument, it can be shown that after putting a vertex into
$V_{0},\,V_{1}$ or $V_{2}$ we will never remove it from these sets again.
Further, after putting a vertex into $\overline{V_{2}}$, it will only go into
$V_{0}$ or $V_{1}$. Since we decide for $A$ vertices to be in either $V_{2}$
or $\overline{V_{2}}$ (together with the use of Reduction Rule 3), this
implies that if the algorithm returns two unique response Roman dominating
functions, then they will not be the same.

###### Claim

Let $(A,\overline{V_{2}},V_{0},V_{1},V_{2})$ be a constellation which is
represented by a node $v$ in the branching tree. Then either we can use
Reduction Rule 1, or there is a constellation
$(\emptyset,\emptyset,V_{0}^{\prime},V_{1}^{\prime},V_{2}^{\prime})$ which is
represented by a leaf of the branching tree below $v$ such that
$f\in\\{0,1,2\\}^{V}$ is a unique response Roman dominating function with
$V_{i}(f)\coloneqq V^{\prime}_{i}$ for $i\in\\{0,1,2\\}$, is a unique response
Roman dominating function.

_Proof._ In each branching rule, the algorithm puts a vertex into $V_{0}$ if
and only if the vertex has a neighbor in $V_{2}$. Further, the neighbors of
$V_{2}$ vertices are all in $V_{0}$. The algorithm puts a vertex into $V_{1}$
only if we use Reduction Rule 3. As the algorithm never puts a vertex from
$\overline{V_{2}}$ into $V_{2}$, $V_{1}\cap N_{G}(V_{2})$ is empty.

Define $g:V\to\\{0,1,2\\}$ with $V_{0}(g):=V_{0}$,
$V_{1}(g)=A\cup\overline{V_{2}}\cup V_{1}$ and $V_{2}(g)=V_{2}$. We get $g$ by
using the last case of each branching rule on
$(A,\overline{V_{2}},V_{0},V_{1},V_{2})$. By our observations from above, $g$
is a unique response Roman dominating function if and only if $|N_{G}(v)\cap
V_{2}|=1$ holds for each $v\in V_{0}(g)=V_{0}$. If this would not hold, then
we could use Reduction Rule 1. $\Diamond$

As we only consider each vertex at most once in a branching, we have to test
Reduction Rule 1 at most $|V|$ times. This test runs in polynomial time.
Therefore, the branching algorithm runs with polynomial delay.

Branching Rule # | Branching vector | Branching number
---|---|---
Branching Rule 1 | $(3,1-\omega)$ | 1.7229
Branching Rule 2 | $(2,2,2)$ | $\sqrt{3}$
Branching Rule 3 | $(1+\omega,1)$ | 1.7218
Table 1: Collection of all branching vectors; the branching numbers are
displayed for the different cases with $\omega=0.6$.

##  5 Extension Perfect Roman Domination

In this section, we will consider Extension Perfect Roman Domination. More
precisely, we will first provide a combinatorial result for deciding if a
function is a (pointwise) minimal perfect Roman dominating function.

###### Lemma 8

Let $G=(V,E)$ be a graph. A function $f:V\rightarrow\\{0,1,2\\}$ is a minimal
perfect Roman dominating function if and only if the following conditions are
true:

  1. 1.

$\forall v\in V_{0}(f):\>|N_{G}(v)\cap V_{2}(f)|=1$,

  2. 2.

$\forall v\in V_{1}(f):\>|N_{G}(v)\cap V_{2}(f)|\neq 1$,

  3. 3.

$\forall v\in V_{2}(f):\>|N_{G}(v)\cap V_{0}(f)|\neq 0$.

###### Proof

Let $f$ be a minimal perfect Roman dominating function. This implies the first
condition. If there exists a $v\in V_{1}(f)$ with $|N_{G}(v)\cap V_{2}(f)|=1$,
then $f-\chi_{\\{v\\}}$ is also a perfect Roman dominating function, cf.
Observation 1. For each $v\in V_{2}(f)$, $|N_{G}(v)\cap V_{0}(f)|\neq 0$, as
otherwise $f-\chi_{\\{v\\}}$ is also a perfect Roman dominating function.

Now assume $f$ is a function that fulfills the three conditions. By the first
condition, we know $f$ is a perfect Roman dominating function. Let $g$ be a
minimal perfect Roman dominating function with $g\leq f$. Therefore,
$V_{0}(f)\subseteq V_{0}(g)$ and $V_{2}(g)\subseteq V_{2}(f)$ hold. Assume
there exists a $v\in V$ with $g(v)<f(v)=2$. By the third condition, there
exists some $u\in N_{G}(v)\cap V_{0}(f)$. Because of condition 1, $v$ is the
only neighbor of $u$ with value 2. This implies that $N_{G}(u)\cap
V_{2}(g)\subseteq N_{G}(u)\cap(V_{2}(g)\setminus\\{v\\})=\emptyset$. This
contradicts the construction of $g$ as a perfect Roman dominating function.
Therefore, $V_{2}(g)=V_{2}(f)$. If there were a $v\in V$ with $g(v)=0<1=f(v)$,
then this contradicts that $g$ is a perfect Roman dominating function, since
$|N_{G}(v)\cap V_{2}(g)|=|N_{G}(v)\cap V_{2}(f)|\neq 1$. ∎

###### Remark 2

This lemma provides that the function $\mathds{1}\colon V\to\\{0,1,2\\}$ is
the maximum minimal perfect Roman dominating function with respect to $\omega$
for each graph $G=(V,E)$, similar to maximum minimal Roman dominating
functions as discussed in [15]. This is the case as if there exists a vertex
$v\in V$ of value $2$ then this vertex needs a neighbor $u$ with value $0$.
Since $u$ has exactly one neighbor in $V_{2}(f)$,
$\omega\left(f\right)\leq|V|$ for each perfect Roman dominating function $f$.

We will use this lemma to show some some hardness results for Extension
Perfect Roman Domination.

Problem name: Extension Perfect Roman Domination
Given:  A graph $G=(V,E)$ and $f\in\\{0,1,2\\}^{V}$. Question:  Is there a
minimal perfect Roman dominating function $g$ on $G$ with $f\leq g$?

###### Remark 3

It should be mentioned that there are graphs $G=(V,E)$ such that the set of
perfect Roman dominating functions on $G$ is not closed under $\leq$. This
means that there exists a perfect Roman dominating function
$f\in\\{0,1,2\\}^{V}$ and a $g\in\\{0,1,2\\}^{V}$ with $f\leq g$ such that $g$
is no perfect Roman dominating function. One example for this is the 4-cycle

$C_{4}=(\\{v_{1},v_{2},v_{3},v_{4}\\},\\{\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},\\{v_{3},v_{4}\\},\\{v_{4},v_{1}\\}\\})$

with the two functions

$f(v_{1})=0$, |  $f(v_{2})=2$, |  $f(v_{3})=0$, |  $f(v_{4})=1$,
---|---|---|---
$g(v_{1})=0$, |  $g(v_{2})=2$, |  $g(v_{3})=0$, |  $g(v_{4})=2$.

This contradicts the idea of extension problems as they are defined in [12],
because this violates the so-called upward closedness condition, but this
condition is a matter of debate even in [12].

###  5.1 $\textsf{W}[1]$-Hardness

In this subsection, we will show $\textsf{W}[1]$-hardness of Extension Perfect
Roman Domination if parameterized by the weight of the pre-solution. As the
reduction will also be polynomial, this will also imply NP-hardness of the
underlying unparameterized problem. For the NP-membership, we simple guess the
value of each vertex (at most $|V|$ steps) and then check the conditions of 8.
For the hardness result, we use Irredundant Set. A set $I\subseteq V$ is
called _irredundant_ if each vertex in $I$ has a private neighbor.

Problem name: Irredundant Set
Given:  A graph $G=(V,E)$ and $k\in\mathbb{N}$ Question:  Is there an
irredundant set $I$ on $G$ with $|I|=k$?

In [17] it is shown that Irredundant Set, parameterized by $k$, is
$\textsf{W}[1]$-complete.

###### Theorem 5.1

Extension Perfect Roman Domination is NP-complete. $k$-Extension Perfect Roman
Domination is $\textsf{W}[1]$-hard (even on bipartite graphs).

###### Proof

For the NP-membership, we simple guess the value of each vertex and check the
conditions of 8.

Let $G=(V,E)$ be a graph and $k\in\mathbb{N}$. Define for each $i\in[k+1]$,
$V_{i}=\\{v_{i}\mid v\in V\\}$ and $G^{\prime}=(V^{\prime},E^{\prime})$ with

$\begin{split}V^{\prime}=\,&\\{a,b,c,d\\}\cup\\{u_{1},\ldots,u_{k}\\}\cup\bigcup_{i=1}^{k+1}V_{i},\\\
E^{\prime}=\,&\\{\\{a,b\\},\\{c,d\\}\\}\\\
\cup\,&\\{\\{a,u_{i}\\},\\{v_{i},u_{i}\\},\\{v_{i},c\\},\\{v_{i},w_{k+1}\\}\mid
v\in V,w\in N_{G}[v],i\in[k]\\}.\end{split}$

We also need $f\in\\{0,1,2\\}^{V^{\prime}}$ with
$V_{0}(f)=\\{b,d\\}\cup\bigcup_{i=1}^{k+1}V_{i},V_{1}(f)=\\{u_{1},\ldots,u_{k}\\}$
and $V_{2}(f)=\\{a,c\\}.$ This implies $\omega(f)=k+4$. $G^{\prime}$ is a
bipartite graph, as we can partition its vertex set into two independent sets
$I_{1}=\\{a,d\\}\cup\\{v_{i}\mid v\in V,i\in[k]\\}$ and
$I_{2}=\\{b,c\\}\cup\\{u_{i}\mid i\in[k]\\}\cup\\{v_{k+1}\mid v\in V\\}$.

Let $I=\\{w^{1},\ldots,w^{k}\\}\subseteq V$ be an irredundant set with
$|I|=k$. Define $g\in\\{0,1,2\\}^{V^{\prime}}$ with

$\begin{split}V_{0}(g)=&\,\\{b,d\\}\cup\\{v_{k+1}\mid v\in V:|N_{G}[v]\cap
I|=1\\}\cup\\{v_{i}\mid i\in[k],v\in V\setminus\\{w^{i}\\}\\},\\\
V_{1}(g)=&\,\\{u_{1},\ldots,u_{k}\\}\cup\\{v_{k+1}\mid v\in V:|N_{G}(v)\cap
I|\neq 1\\},\\\
V_{2}(g)=&\,\\{a,c\\}\cup\\{w_{1}^{1},\ldots,w_{k}^{k}\\}.\end{split}$

$=\\{w_{k+1}\mid w\in N_{G}[v]\\}$$v_{i}$$u_{i}$$a$$b$$c$$d$⋮ Figure 1:
Construction for Theorem 5.1, for each $v\in V$ and $i\in[k]$.

Clearly, $f\leq g$ holds. The vertex $b$ is a private neighbor of $a$, and $d$
is one of $c$. For each $i\in[k]$, $g(w^{i}_{i})=2$ implies
$|N_{G^{\prime}}(u_{i})\cap V_{2}(g)|\geq 2$. Since $I$ is irredundant, for
each $w^{i}\in I$, there is a private neighbor $p^{i}$ in $G$ and hence, for
each $w^{i}_{i}$, there is a private neighbor $p^{i}_{k+1}\in\\{v_{k+1}\mid
v\in V\\}$ in $G^{\prime}$. As $g$ clearly is a Roman domination function, it
is hence also a perfect Roman dominating function by Observation 1.
Furthermore, for all $i\in[k]$ and $v\in V\setminus\\{w^{i}\\}$,
$\\{c\\}=N_{G^{\prime}}(v_{i})\cap V_{2}(g)$ holds. By the construction of
$g$, all vertices in $v_{k+1}$ with $v\in V$ have the correct value for $g$ to
be a minimal perfect Roman dominating function.

Assume we have a minimal perfect Roman dominating function $g$ on $G^{\prime}$
with $f\leq g$. For all $i\in[k]$,
$N_{G^{\prime}}(u_{i})=\\{a\\}\cup\\{v_{i}\mid v\in V\\}\subseteq\\{a\\}\cup
N_{G^{\prime}}(c)$. As $f(c)=g(c)=2$, this implies that $g(u_{i})=1$ and that
$V_{i}\cap V_{2}(g)$ is not empty by 8. Let $w^{i}_{i}$ be such a vertex for
each $i\in[k]$. Define $I=\\{w^{1},\ldots,w^{k}\\}\subseteq V$. As for each
$i\in[k]$, all vertices in $V_{i}$ are already dominated by $c$, the private
neighbor of $w_{i}^{i}$ has to be $p^{i}_{k+1}\in V_{k+1}$ and hence, $p^{i}$
is a private neighbor of $w^{i}$ in $G$. Therefore, $I$ is an irredundant set
with $|I|=k$. ∎

This result implies that it is unlikely to have an FPT algorithm for
$k$-Extension Perfect Roman Domination (unless $\textsf{W}[1]=\textsf{FPT}$).
Nonetheless, we can provide an XP algorithm below.

As $|V_{2}(f)|=2$ and $|V_{1}(f)|=k$, we get the following corollary.

###### Corollary 4

$|V_{1}(f)|$-Extension Perfect Roman Domination is $\textsf{W}[1]$-hard and
$|V_{2}(f)|$-Extension Perfect Roman Domination is para-NP-hard.

###  5.2 XP-Membership

As we ruled out membership in FPT under standard complexity assumptions in the
previous subsection, the next best algorithmic fact one could hope for is
membership in XP, a class that is also dubbed ‘poor man’s FPT’. In the
following, we will provide an explicit XP-algorithm, allowing a running time
of $\mathcal{O}^{*}(n^{k})$ on graphs of order $n$. Notice that in the next
subsection, we even prove membership in $\textsf{W}[1]$. From this membership,
one can also deduce membership in XP, but without having an implementable
algorithm in hands. Further, the XP algorithm implies some theoretical results
which we need for the $\textsf{W}[1]$ membership proof. As testified in [36]
for quite related problems (also confer the discussions in [22]), also XP-
algorithms of the proposed form could be very helpful in practical
implementations.

###### Lemma 9

Let $G=(V,E)$ be a graph and $f\in\\{0,1,2\\}^{V}$ such that for each $u\in
V_{1}(f)$, $|N_{G}(u)\cap V_{2}(f)|\neq 1$ and for each $v\in V_{2}(f)$, there
exists a private neighbor in $V_{0}(f)$ with respect to $G$ and $V_{2}(f)$.
Then there exists a minimal perfect Roman dominating function
$g\in\\{0,1,2\\}^{V}$ on $G$ with $f\leq g$ and $V_{2}(f)=V_{2}(g)$.

###### Proof

Let $A=\\{v\in V_{0}(f)\mid|N_{G}(v)\cap V_{2}(f)|\neq 1\\}$. Define
$g=f+\chi_{A}$. Clearly, $f\leq g$ and $V_{2}(f)=V_{2}(g)$. This leaves to
show that $g$ is a minimal perfect Roman dominating function.

By definition of $A$, for each $v\in V_{0}(g)=V_{0}(f)\setminus A$,
$1=|N_{G}(v)\cap V_{2}(f)|=|N_{G}(v)\cap V_{2}(g)|$. Further for all $v\in
V_{1}(g)=V_{1}(f)\cup A$, $1\neq|N_{G}(v)\cap V_{2}(f)|$. Let $v\in V_{2}(g)$.
By the requirement on $V_{2}(f)=V_{2}(g)$, for $v\in V_{2}(g)$ there exists a
private neighbor $u\in V_{0}(f)$. Thus, $|N_{G}(u)\cap V_{2}(f)|=1$ and $u\in
V_{0}(f)\setminus A=V_{0}(g)$. Hence $N_{G}(v)\cap V_{0}(f)\neq\emptyset$ for
all $v\in V_{2}(f)$. In total $g$ is a minimal Roman dominating function. ∎

The proof gives also an algorithm to compute the minimal perfect Roman
dominating function from the given function $f$. We only have to compute
$A\subseteq V_{0}(f)$ as specified in the proof, which can be done in
polynomial time.

###### Lemma 10

Let $G=(V,E)$ be graph and $f\in\\{0,1,2\\}^{V}$. Then there exists a minimal
perfect Roman dominating function $g\in\\{0,1,2\\}$ with $f\leq g$ and
$V_{2}(f)=V_{2}(g)$ if and only if each $v\in V_{2}(f)$ has a private neighbor
in $V_{0}(f)$ (with respect to $G$ and $V_{2}(f)$) and $|N_{G}(u)\cap
V_{2}(f)|\neq 1$ for each $u\in V_{1}(f)$.

###### Proof

The if-part follows directly by 9.

For the only if part, assume there exists a minimal perfect Roman dominating
function $g$ on $G$ with $f\leq g$ and $V_{2}(f)=V_{2}(g)$. Hence,
$V_{0}(g)\subseteq V_{0}(f)$ and $V_{1}(f)\subseteq V_{1}(g)$. Since $g$ is a
minimal perfect Roman dominating function, Conditions 1 and 3 hold. This
implies that each $v\in V_{2}(g)=V_{2}(f)$ has a private neighbor in
$V_{0}(g)\subseteq V_{0}(f)$. For each $u\in V_{1}(g)$, $|N_{G}(u)\cap
V_{2}(f)|=|N_{G}(u)\cap V_{2}(g)|\neq 1$. As $V_{1}(f)\subseteq V_{1}(g)$,
this also holds for all $u\in V_{1}(f)$. ∎

Now we can prove that Algorithm 1 is an XP algorithm.

Algorithm 1 Solving instances of ExtPRD

1:procedure ExtPRD Solver($G,f$)
Input: A graph $G=\left(V,E\right)$ and a function $f\colon V\to\\{0,1,2\\}$.
Output: Is there a minimal perfect Roman dominating function $\widetilde{f}$
with $f\leq\widetilde{f}$?

2: for $v\in V_{2}(f)$ do

3: $x\coloneqq 0$

4: for $w\in V_{0}(f)\cap V_{2}(f)$ do

5: if $|N(w)\cap V_{2}(f)|=1$ then $x=1$

6: if $x=0$ then return no

7: for $v\in V_{1}(f)$ do

8: if $|N(v)\cap V_{2}(f)|=1$ then

9: for $u\in N(v)\setminus V_{2}(f)$ do

10: $f_{u}\coloneqq f$

11: Set $f_{u}(u)=2$

12: if ExtPRD Solver$(G,f_{u})$ then return yes

13: return no

14: return yes

###### Theorem 5.2

Algorithm 1 is an XP algorithm for $k$-Extension Perfect Roman Domination for
$k\in\\{\omega\left(f\right),|V_{1}(f)|\\}$. Let $(G,f)$ with $G=(V,E)$ and
$f\in\\{0,1,2\\}^{V}$ be an instance of Extension Perfect Roman Domination. If
the algorithm returns a minimal perfect Roman dominating function $g$, then
$|V_{2}(g)|\leq\omega\left(f\right)$.

###### Proof

Let $G=(V,E)$ be graph and $f\in\\{0,1,2\\}^{V}$. Since
$|V_{1}|\leq\omega\left(f\right)$, we only need to consider $|V_{1}(f)|$ as
parameterization. At first we explain the algorithm. The idea is modify $f$
such that it fulfills the conditions of 9. Therefore, we look if each $v\in
V_{2}(f)$ has a private neighbor in $V_{0}(f)$. If this is not the case, then
there exists no minimal perfect Roman dominating function bigger than $f$. If
each $v\in V_{2}(f)$ has a private neighbor in $V_{0}(f)$, we look if there
exists a $u\in V_{1}(f)$ with $|N_{G}(u)\cap V_{2}(f)|=1$. If this is not the
case, then $f$ itself already fulfills the condition of 9. Otherwise, we go
through all neighboring vertices $v\in N_{G}(u)\setminus V_{2}(f)$ and try the
algorithm with

$f_{v}\colon V\to\\{0,1,2\\},\,x\mapsto\begin{cases}2,&x=v\\\ f(x),&x\neq
v\end{cases},$

_i.e._ , $f_{v}=f+(2-f(v))\cdot\chi_{\\{v\\}}$. Since we only return yes (or a
minimal perfect Roman dominating function) if $f$ verifies the condition of 9
and we only increase $f$, there exists a minimal perfect Roman dominating
function $g\in\\{0,1,2\\}$ with $f\leq g$ if we return yes (or a minimal
perfect Roman dominating function).

Assume there exists a minimal perfect Roman dominating function, say $g$, with
$f\leq g$. This implies $V_{2}(f)\subseteq V_{2}(g)$ and $V_{0}(g)\subseteq
V_{0}(f)$. We prove that the algorithm will return a minimal perfect Roman
dominating function by an induction argument on $\omega(g-f)$.

If $\omega(g-f)=0$, $f=g$ holds. Then each vertex $V_{2}(f)$ has a private
neighbor in $V_{0}(f)$. Otherwise, it would contradict 8, Condition 3.
Further, for $f=g$ there exists no vertex $v\in V_{1}(f)$ with $|N_{G}(v)\cap
V_{2}(f)|=1$ because of Condition 2 of 8.

Assume $\omega(g-f)=1$. Then there exists exactly one vertex in $v\in V$ with
$f(x)\neq g(v)$. More precisely, $f(v)=g(v)-1$. First, we consider the case
$f(v)=0$. This implies that $V_{2}(f)=V_{2}(g)$. By 10, $f$ fulfills the
conditions of 9. Now assume $f(v)=1$. This implies $V_{0}(f)=V_{0}(g)$ and
$V_{2}(g)=V_{2}(f)\cup\\{v\\}$. Therefore, for each $u\in V_{2}(f)\subseteq
V_{2}(g)$, there exists a private neighbor in $N_{G}(u)\cap
V_{0}(g)=N_{G}(u)\cap V_{0}(f)$. If each $u\in V_{1}(f)$ fulfills
$|N_{G}(u)\cap V_{2}(f)|\neq 1$, then our algorithm would make use of 9.
Assume there exists a $u\in V_{1}(f)$ with $\\{w\\}=N_{G}(u)\cap V_{2}(f)$. If
$u\notin N_{G}(v)$, then $|N_{G}(u)\cap V_{2}(g)|=1$ would contradict the
minimality of $g$. Therefore, $v\in N_{G}(u)$. Since $|N_{G}(u)\cap
V_{2}(g)|=1$ holds, our algorithm would try, for each $x\in
N_{G}[u]\setminus\\{w\\}$, if there exists a minimal perfect Roman dominating
function $h\in\\{0,1,2\\}^{V}$ such that $f_{x}\leq h$. Hence, our algorithm
would also consider $f_{v}=g$ (see above).

Let $\omega(g-f)>2$ and and assume that $f$ does not fulfill the conditions of
9. Hence, $f\neq g$. Recall $V_{2}(f)\subseteq V_{2}(g)$ and
$V_{0}(g)\subseteq V_{0}(f)$. Therefore, for each $v\in V_{2}(f)\subseteq
V_{2}(g)$, there exists a $u\in N_{G}(v)\cap V_{0}(g)\subseteq N_{G}(v)\cap
V_{2}(f)$ with $N_{G}(u)\cap(V_{2}(f)\setminus\\{v\\})\subseteq
N_{G}(u)\cap(V_{2}(g)\setminus\\{v\\})=\emptyset$. This implies that each
$v\in V_{2}(f)$ has a private neighbor in $V_{0}(f)$. Since the algorithm does
not return a minimal perfect Roman dominating function, there exists a $u\in
V_{1}(f)$ with $\\{v\\}=N_{G}(u)\cap V_{2}(f)$. As $g$ is minimal, there must
exist a $w\in(N_{G}(v)\cap V_{2}(g))\setminus\\{u\\}$. Therefore, we consider
$f_{x}$ for each $x\in N_{G}[u]\setminus\\{v\\}$ (so also for $w$). By
induction and $\omega(g-f_{w})<\omega(g-f)\leq\omega(g-f_{w})+2$, it follows
that we find a minimal perfect Roman dominating function $f^{\prime}$ on $G$
with $f\leq f^{\prime}$. Hence, the algorithm runs correctly.

Now, we consider the running time of the algorithm. Checking if each vertex in
$V_{2}(f)$ has a private neighbor in $V_{0}(f)$ can be done in polynomial time
(in time $\mathcal{O}(|V|^{3})$ with a naive algorithm). Further, we can test
in polynomial time if there exists a $u\in V_{1}(f)$ with $|N_{G}(u)\cap
V_{2}(f)|=1$ (in time $\mathcal{O}(|V|^{2})$ with a naive algorithm). If this
is the case, then we go through $w\in N_{G}[u]\setminus V_{2}(f)$ and run the
algorithm on on $f_{w}$. Clearly $V_{0}(f_{w})\subseteq V_{0}(f)$ and
$V_{1}(f_{w})\subseteq V_{1}(f)$ and $V_{2}(f)\cup\\{w\\}=V_{2}(f_{w})$.
Together with $|N_{G}(u)\cap V_{2}(f_{w})|>1$, this implies that
$|N_{G}(u)\cap V_{2}(h)|\neq 1$ will hold for all $h\in\\{0,1,2\\}^{V}$ with
$f_{w}\leq h$. Thus, we add only one vertex to $V_{2}(f)$ per vertex in
$V_{1}(f)$. As we never add a vertex to $V_{1}(f)$ (unless we use 9, but then
we already know that there is a solution), the recursion tree has at most
$|V_{1}(f)|\leq k$ many nodes between the root and a leaf. This also proves
the bound on the size of $V_{2}(h)$ for a solution $h$ returned by the
algorithm. As there are at most $|V|$ choices for $w$, we call the recursive
function at most $n^{k}$ times. Therefore, it is an XP algorithm. ∎

The proof of the last theorem implies the following corollary.

###### Corollary 5

Let $G=(V,E)$ be a graph and $f\in\\{0,1,2\\}^{V}$ with
$k\coloneqq\omega\left(f\right)$. If there exists a minimal perfect Roman
domination function $h$ on $G$ with $f\leq h$, then there exists a minimal
perfect Roman domination function $g$ with $|V_{2}(g)\setminus
V_{2}(f)|\leq|V_{1}(f)|$, $|V_{2}(g)|\leq k$ and $f\leq g$.

The very existence of an XP-algorithm with respect to $|V_{1}(f)|$ is
interesting, as the very similarly looking parameterized problem
$|V_{1}(f)|$-Extension Roman Hitting Set is para-NP-hard (see [22]). Moreover,
we need this corollary in order to prove $\textsf{W}[1]$-membership in the
next subsection, so that we cannot derive XP-membership without the
considerations of this subsection.

###  5.3 $\textsf{W}[1]$-Membership

We do not only provide a hardness result (presented in the previous
subsection) but also a complete classification of
$\omega\left(f\right)$-Extension Perfect Roman Domination.

###### Lemma 11

Let $G=(V,E)$ be a graph and $f\in\\{0,1,2\\}^{V}$ with
$k\coloneqq\omega\left(f\right)$. There exists a minimal perfect Roman
dominating function $g$ on $G$ with $f\leq g$ if and only if there exists a
$V^{\prime}\subseteq V$ with $|V^{\prime}|\leq k$ and $V_{2}\subseteq
V^{\prime}$ such that each $v\in V^{\prime}$ has a private neighbor in
$V_{0}(f)\setminus V^{\prime}$ with respect to $G$ and $|N_{G}(u)\cap
V^{\prime}|\neq 1$ for each $u\in V_{1}(f)\setminus V^{\prime}$.

###### Proof

Let $g$ be a minimal perfect Roman dominating function on $G$ with $f\leq g$.
By 5, there exists a minimal perfect Roman dominating function $g^{\prime}$ on
$G$ with $f\leq g^{\prime}$ and $|V_{2}(g^{\prime})|\leq k$. As $f\leq
g^{\prime}$, $V_{2}(f)\subseteq V^{\prime}\coloneqq V_{2}(g^{\prime})$,
$V_{0}(g^{\prime})\subseteq V_{0}(f)\setminus V^{\prime}$ and
$V_{1}(f)\setminus V^{\prime}\subseteq V_{1}(g^{\prime})$. Since $g^{\prime}$
is minimal perfect Roman dominating function, each $v\in V^{\prime}$ has a
neighbor in $V_{0}(g^{\prime})\subseteq V_{0}(f)\setminus V^{\prime}$. By the
definition of perfect Roman dominating function, this neighbor is private. For
$u\in V_{1}(f)\setminus V^{\prime}\subseteq V_{1}(g^{\prime})$, $|N_{G}(u)\cap
V^{\prime}|\neq 1$. Therefore $V^{\prime}$ fulfills the conditions.

Let $V^{\prime}$ be a set that verifies the condition. Then
$f^{\prime}:V\to\\{0,1,2\\}$ with $V_{0}(f^{\prime})=V_{0}(f)\setminus
V^{\prime}$, $V_{1}(f^{\prime})=V_{1}(f)\setminus V^{\prime}$ and
$V_{2}(f^{\prime})=V^{\prime}$ fulfills the conditions of 10. Hence, there
exists a minimal perfect Roman dominating function $g$ on $G$ with $f\leq
f^{\prime}\leq g$. ∎

We will use this result to show $\textsf{W}[1]$-membership by a reduction with
Short Non-Deterministic Turing Machine Computation.

Problem name: Short Non-Deterministic Turing Machine Computation
Given:  A nondeterministic one-tape Turing machine TM, a word $w$ and
$k\in\mathbb{N}$ Parameter:  $k$ Question:  Does TM accept $w$ in at most $k$
steps?

###### Theorem 5.3

$k$-Extension Perfect Roman Domination is $\textsf{W}[1]$-complete.

###### Proof

We only need to prove $\textsf{W}[1]$-membership. Therefore, let $G=(V,E)$ be
a graph and $f\in\\{0,1,2\\}^{V}$ be a function with
$V_{1}(f)\coloneqq\\{u^{1},\ldots,u^{\ell}\\}$ and
$V_{2}(f)=\\{v^{1},\ldots,v^{\ell^{\prime}}\\}$ ($\ell+2\ell^{\prime}=k$ and
$0\leq\ell,\ell^{\prime}$).

The idea of our nondeterministic Turing machine (NTM for short) is to guess at
most $k$ new vertices in $V_{2}(g)$ for a perfect Roman dominating function
$g$ with $f\leq g$. After this we check if the vertices satisfy the conditions
of 10. For the private neighborhood condition we guess for each vertex which
vertex is the private neighbor and check if this vertex is the private
neighbor and if the vertex is in $V_{0}(f)$. For the second condition we go
for each $u\in V_{1}(f)$ through the vertices and count the number of
neighbors up to two.

Now we will describe how the NTM works. The input alphabet is given by the
vertex set. Then, $\Gamma\coloneqq\\{b\\}\cup V\cup\\{v_{i}\mid v\in
V,i\in[k]\\}$ ($|\Gamma|=|V|\cdot(k+1)$) denotes the tape alphabet for which
$b$ is the blank symbol. Define the set of states by

$\begin{split}Q\coloneqq{}&\\{q_{f}\\}\cup\\{s_{1},\ldots,s_{\ell^{\prime}}\\}\cup\\{q_{\text{fill},\ell^{\prime}+1},\ldots,q_{\text{fill},k+1}\\}\cup\\{q_{w}^{j,i}\mid
w\in V,\,i,j\in[k],\,i<j\\}\\\ {}\cup{}&\\{q_{L}^{j,i}\mid
i,j\in[k],i<j\\}\cup\\{q_{j}^{0},q_{j}^{1},q_{L,j}\mid
j\in[\ell]\\}.\end{split}$

There is only the final state $q_{f}$ and $s_{1}$ is the start state. The
number of states is at most $k^{2}\cdot(|V|+1)+\mathcal{O}(k)$. The input word
is just $\ldots,b,v^{1},\ldots,v^{\ell^{\prime}},b,\ldots$ . Now we will
present all transitions:

  1. 1.

$((s_{i},v^{i}),(s_{i+1},v^{i}_{i},R))$ for all $v\in V_{2}(f)$ and
$i\in[\ell^{\prime}-1]$,111Let us briefly explain how we write down the
transitions of a Turing machine using this example. This transition can be
activated if the TM is in state $s_{i}$ and currently reads the symbol
$v^{i}$. It can then move to state $s_{i+1}$, replace the symbol $v^{i}$ by
$v^{i}_{i}$ and then move to the right.

  2. 2.

$((s_{\ell^{\prime}},v^{\ell^{\prime}}),(q_{\text{fill},\ell^{\prime}+1},v_{\ell^{\prime}}^{\ell^{\prime}},R))$

  3. 3.

$((q_{\text{fill},i},b),(q_{\text{fill},i+1},v_{i},R))$ for all
$i\in[k]\setminus[\ell^{\prime}]$ and $v\in V$,

  4. 4.

$((q_{\text{fill},i},b),(q_{L}^{i-1},b,L))$ for all
$i\in[k+1]\setminus\\{1\\}$,

  5. 5.

$((q_{L}^{i},v_{p}),(q_{L}^{i},v_{p},L))$ for all $v\in V$ and $i,p\in[k]$
with $p\leq i$,

  6. 6.

$((q_{L}^{i},b),(q_{w}^{1,i},b,R))$ for all $w\in V$ and $i\in[k]$,

  7. 7.

$((q_{w}^{t,i},v_{t}),(q_{w}^{t,i},v_{t},R))$ for all $\\{v,w\\}\in E$ and
$t,i\in[k]$ with $t\leq i$,

  8. 8.

$((q_{w}^{t,i},v_{j}),(q_{w}^{t,i},v_{j},R))$ for all $v,w\in V$ and
$i,j,t\in[k]$ with $v\notin N_{G}[w]$ and $j,t\leq i$,

  9. 9.

$((q_{w}^{t,i},b),(q_{L}^{t,i},b,L))$ for all $w\in V\setminus V_{1}(f)$ and
$i,t\in[k]$ with and $t\leq i$,

  10. 10.

$((q_{L}^{t,i},v_{j}),(q_{L}^{t,i},v_{j},L))$ for all $v\in V$ and
$i,j,t\in[k]$ with $j,t\leq i$,

  11. 11.

$((q_{L}^{t,i},b),(q_{w}^{t+1,i},b,R))$ for all $w\in V$ and $i,t\in[k]$ with
$t<i$,

  12. 12.

$((q_{L}^{i,i},b),(q_{1}^{0},b,R))$ for all $w\in V$ and $i\in[k]$,

  13. 13.

$((q_{t}^{0},v_{j}),(q_{t}^{0},v_{j},R))$ for all $v\in V$, $t\in[\ell]$ and
$j\in[k]$ with $v\notin N_{G}[u^{t}]$,

  14. 14.

$((q_{t}^{0},v_{j}),(q_{t}^{1},v_{j},R))$ for all $v\in V$, $t\in[\ell]$ and
$j\in[k]$ with $\\{v,u^{t}\\}\in E$,

  15. 15.

$((q_{t}^{0},v_{j}),(q_{L,t},v_{j},L))$ for all $v\in V$, $t\in[\ell]$ and
$j\in[k]$ with $v=u^{t}$,

  16. 16.

$((q_{t}^{0},b),(q_{L,t},b,L))$ for all $t\in[\ell]$,

  17. 17.

$((q_{t}^{1},v_{j}),(q_{t}^{1},v_{j},R))$ for all $v\in V$, $t\in[\ell]$ and
$j\in[k]$ with $v\notin N_{G}[u^{t}]$,

  18. 18.

$((q_{t}^{1},v_{j}),(q_{L,t},v_{j},L))$ for all $v\in V$, $t\in[\ell]$ and
$j\in[k]$ with $v\in N_{G}[u^{t}]$,

  19. 19.

$((q_{L,t},v_{j}),(q_{L,t},v_{j},L))$ for all $v\in V$, $t\in[\ell]$ and
$j\in[k]$,

  20. 20.

$((q_{L,t},b),(q_{t+1}^{0},b,R))$ for all $t\in[\ell]$,

  21. 21.

$((q_{L,\ell},b),(q_{f},b,L))$.

For the proof we will divide a run of the NTM into three phases and prove
claims for each phase separately. The first phase is from the beginning to the
(only) use of the transition 6. In this phase, we guess $V_{2}(g)$ of our
would-be solution $g$.

At the beginning of the run, we are in the state $s_{1}$ and at the leftmost
position of the tape with a non-blank symbol ($v^{1}$ is in this position). By
an easy inductive argument, we can prove that after $\ell^{\prime}$ steps,
$\ldots,b,v_{1}^{1},\ldots,v^{\ell^{\prime}}_{\ell^{\prime}},b,\ldots$ is
written on the tape and the tape head is to the right of
$v_{\ell^{\prime}}^{\ell^{\prime}}$ and the TM is in the state
$q_{\text{fill},\ell^{\prime}+1}$. Keep in mind that the states
$s_{1},\ldots,s_{\ell^{\prime}}$ occur only in the transitions 1, being
mentioned in increasing order. Therefore, we will never get into these states
again.

The next step is the first nondeterministic step. Here the Turing machine
guesses, if it uses a transition of 4 or uses for a $v\in V$ the transition

$((q_{\text{fill},\ell^{\prime}},b),(q_{\text{fill},\ell^{\prime}+1},v_{\ell^{\prime}+1},R))\,.$

If the Turing machine uses the second case, _i.e._ , when a new (encoded)
vertex has been written on the tape, then it has to guess again if it moves
into the state $q_{L}^{i}$ or if it writes a new vertex on the tape
($\ell^{\prime}\leq i\leq k$). After at most $k+1$ steps, we have to use a
transition from 4, as for $q_{\text{fill},k+1}$ there is only one transition.

Assume that after $i$ steps (with $\ell^{\prime}\leq i\leq k$) we use a
transition from 4. Then we are in the state $q_{L}^{i}$ and
$\ldots,b,v_{1}^{1},\ldots,v_{i}^{i},b\ldots$ is written on the tape. More
precisely, the initial string $v^{1}\cdots v^{\ell^{\prime}}$ that was the
input of the TM has been converted into the prefix $v^{1}_{1}\cdots
v^{\ell^{\prime}}_{\ell^{\prime}}$, while the suffix
$v^{\ell^{\prime}+1}_{\ell^{\prime}+1}\cdots v_{i}^{i}$ is the part that was
nondeterministically guessed. Since the NTM is never going in to the states
$s_{1},\ldots,s_{\ell^{\prime}}$ again and 2 and 3 are the only transitions
with a $q_{\text{fill},j}$ on the right side for
$j\in[k]\setminus[\ell^{\prime}]$, the Turing machine never goes back into
these states. From now on, the next $i$ steps are deterministic. By an easy
inductive argument again, the tape head moves to the position to the left of
$v_{1}^{1}$. At this point, the first phase ends. This phase needed $2i+1\leq
2k+1$ steps. As we never use the transitions from 1 to 6 again, the symbols on
the tape do not change anymore, _i.e._ , during the remaining run,
$\ldots,b,v_{1}^{1},\ldots,v_{i}^{i},b\ldots$ will stay on the tape, where
$v^{1},\ldots,v^{i}\in V$ are not necessary different vertices. Since
$q_{\text{fill},j}$ had to choose any vertex from $V_{2}(f)$,
$V^{\prime}\coloneqq\\{v^{1},\ldots,v^{i}\\}$ could be any set of size at most
$i$ with $V_{2}(f)\subseteq V^{\prime}$.

The next phase deals with the privacy condition of the vertices on the tape.
This will also ensure that no vertex is written twice on the tape. This phase
will end with the use of a transition from 12. The transitions in 6 and 11 are
nondeterministic, as the Turing machine guesses the vertex $w$. Let $t\in[i]$
and $w\in V_{1}(f)$. The idea of the state $q_{w}^{t,i}$ is to check if $w$ is
the private neighbor of $v^{t}$ (and $v^{t}\neq w$) with respect to
$V^{\prime}$. Let $j\in[i]$. If $j=t$, then there is a deterministic step if
and only if $w\in N_{G}(v_{t})$ (see 7). Otherwise, the Turing machine stops
(in a non-final state), as there is no transition the NTM can use. For $j\neq
t$ the Turing machine will only stop (in a non-final state) if and only if
$w\in N_{G}[v_{j}]$. Otherwise, it performs a deterministic step and goes on
with the next symbol (vertex) $v_{j+1}$ (see 8). In other words, the Turing
machine stops in the state $q_{w}^{t,i}$ if and only if $w$ is not a private
neighbor of $v_{t}$ and $v_{t}\neq w$. This can be proven by induction again.
If the Turing machine made $i$ steps in the state $q_{w}^{t,i}$, the head is
at the end of the word $v_{1}^{1},\ldots,v^{i}_{i}$ and goes back with the
state $q^{t,i}_{L}$ to the beginning (see 9 and 10). Then, the state changes
to $q_{w}^{t+1,i}$ for $t\in[i-1]$ (see 11) or it goes into the new state
$q_{1}^{0}$ for $t=i$ (see 12). Therefore, after $2i^{2}$ steps in this phase,
the Turing machine is still running if and only if each vertex $V^{\prime}$
has a private neighbor in $V\setminus(V_{1}(f)\cap V^{\prime})$. This ends the
second phase.

The third phase will check if each $u\in V_{1}(f)\setminus V^{\prime}$
verifies $|N_{G}(u)\cap V^{\prime}|\neq 1$. Then 11 implies that there exists
a minimal perfect Roman dominating function $g$ on $G$ with $f\leq g$. The
idea of the state $q_{t}^{z}$ for $t\in[\ell]$ and $z\in\\{0,1\\}$, is that
the index $z$ counts how many neighbors of $u^{t}$ we have seen so far.

Let $t\in[\ell]$. Assume we are in the state $q_{t}^{0}$ and at the current
position on the tape, there is $v_{j}^{j}$ for $j\in[i]$. If $v^{j}=u^{t}$,
then $u^{t}\in V^{\prime}\cap V_{1}(f)$. Thus, we do not need to consider
$u^{t}$ anymore and we switch into the state $q_{L,t}$ (see 15). If $v_{j}\in
N_{G}(u)$, the Turing machine has seen a neighbor and goes on with the state
$q_{t}^{1}$ (see 14). Otherwise, we just go to the right, staying in the same
state (see 13). In the case when the tape head is at the right end of the word
in the state $q^{0}_{t}$, this implies that $u^{t}$ has no neighbor in
$V^{\prime}$. Therefore, the NTM switches the state to $q_{L,t}$ (see 19).

Assume we are in the state $q_{t}^{1}$. Keep in mind that the NTM only goes
into the state $q_{t}^{1}$ if and only if the vertex under the current head
position is in the neighborhood of $u^{t}$. For $v^{j}\in N_{G}[u^{t}]$,
either $u^{t}=v^{j}\in V^{\prime}\cap V_{1}(f)$ or $|N_{G}(u^{t})\cap
V^{\prime}|>1$. In both cases, we need not consider $u^{t}$ anymore and the
Turing machine can switch into the state $q_{L,t}$ (see 18). If $v_{j}\notin
N_{G}(u^{t})$, the NTM only goes to the right on the tape (see 17). By an
inductive argument, we can show that the NTM ends in the state $q_{t}^{i}$ on
a cell containing $b$ if and only if $u^{t}$ has exactly one neighbor in
$V^{\prime}$. In this case, the Turing machine would stop in a non-final
state. This implies that the NTM uses the transition 21 after at most
$2\ell\cdot i$ steps in the last phase if and only if for each $t\in[\ell]$,
$|N_{G}(u^{t})\cap V^{\prime}|\neq 1$.

In total, the Turing machine reaches $q_{f}$ in at most
$2i+1+2i^{2}+2\ell\cdot i\leq k^{\prime}\coloneqq 4k^{2}+2k+1$ steps if and
only if there exists a vertex set $V^{\prime}\supseteq V_{2}(f)$ with
$|V^{\prime}|\leq k$ such that each $v\in V^{\prime}$ has a private neighbor
in $V_{0}(f)\setminus V^{\prime}$ and for each $u\in V_{1}(f)\setminus
V^{\prime}$, $|N_{G}(u)|\neq 1$. By 11, the Turing machine ends in a final
state (after at most $k^{\prime}$ steps) if and only if there exists a minimal
perfect Roman dominating function $g$ on $G$ with $f\leq g$. ∎

###  5.4 $|V_{0}(f)|$-Extension Perfect Roman Domination

The main goal of this subsection is to prove the $\textsf{W}[2]$-completeness
of this parameterized problem. We start with some small observations.

###### Lemma 12

$|V_{0}(f)\cup V_{1}(f)|$-$\textsc{Extension Perfect Roman Domination},\\\
\omega\left(2-f\right)$-$\textsc{Extension Perfect Roman
Domination}\in\textsf{FPT}$.

The proof works analogously to Theorem 55 of [22].

###### Proof

For the proof we go trough all possible functions $g\in\\{0,1,2\\}^{V}$ with
$f\leq g$ and check if $g$ is a minimal perfect Roman dominating function
(such a check runs in polynomial time). Let $v\in V$. If $f(v)=2$, then
$g(v)=2$. For $v\in V_{1}(f)$, there are two choices for $g(v)$. If $f(v)=0$
then $g(v)\in\\{0,1,2\\}$. Since $|V_{0}(f)\cup
V_{1}(f)|\leq\omega\left(2-f\right)$ and for each vertex in $V_{0}(f)\cup
V_{1}(f)$ there are at most 3 choices, there up to $3^{k}$ possibilities to
check for $k\in\\{|V_{0}(f)\cup V_{1}(f)|,\omega\left(2-f\right)\\}$. Hence,
there is a FPTalgorithm for both parameterizations.

For $\omega\left(2-f\right)$ as parameterization are even
$2^{\omega\left(2-f\right)}$ many possibilities. For the details take a look
into [22].

###### Lemma 13

Let $G=(V,E)$ be a graph and $f\in\\{0,1,2\\}^{V}$ a function. For a minimal
perfect Roman dominating function $g$ on $G$ with $f\leq g$,
$|V_{2}(g)|\leq|V_{0}(f)|$.

###### Proof

As mentioned before, $V_{0}(g)\subseteq V_{0}(f)$. Further, $|N_{G}(v)\cap
V_{2}(g)|=1$ for each $v\in V_{0}(g)$, by 8. Therefore, there exists a
function $\phi:V_{0}(g)\to V_{2}(f)$, which maps a vertex to its unique
neighbor in $V_{2}(f)$. By 8, each vertex in $V_{2}(g)$ has at least one
neighbor in $V_{0}(g)$. Thus, $\phi$ is surjective. Hence,
$|V_{2}(g)|\leq|V_{0}(g)|\leq|V_{0}(f)|$. ∎

From this lemma we can we can provide a simple XP algorithm with the
parameterization $|V_{1}(f)|$. We know that if there exists a minimal perfect
Roman dominating function $g$ with $f\leq g$ then $|V_{2}(g)|\leq|V_{0}(f)|$.
Therefore, we guess the at most $|V_{0}(f)|$ many vertices in $V_{2}(g)$ and
use 10 on the new function.

Nonetheless, Algorithm 1 is also an XP algorithm with respect to the
parameterization $|V_{0}(f)|$. The running time result follows as on one path
of the branching tree we can only add $|V_{0}(f)|$ vertices to $V_{2}(f)$.
Otherwise, not each vertex in $V_{2}(f)$ will have private in $V_{0}(f)$.
Therefore, the depth of the branching tree is at most $|V_{0}(f)|$.

For the membership, we use a reduction using the problem Short Blind Non-
Deterministic Multi-Tape Turing Machine Computation which was introduced by
Cattanéo and Perdrix in [13]. In that paper, they have also shown
$\textsf{W}[2]$-completeness of this Turing machine problem. The difference
between a _blind_ multi-tape nondeterministic and a normal multi-tape
nondeterministic Turing machine is that the transitions can be independent of
the symbols that are in the cells under the current head positions, _i.e._ ,
the Turing machine may, but need not read the cell contents, and in this
sense, it may be blind.222Possibly, _oblivious_ would have been a better term
for this property, but we stick to the notion _blind_ as introduced in the
mentioned paper.

Problem name: Short Blind Non-Deterministic Multi-Tape Turing Machine
Computation
Given:  A nondeterministic multi-tape Turing machine TM, a word $w$ and
$k\in\mathbb{N}$ Parameter:  $k$ Question:  Does TM accept $w$ in at most $k$
steps?

###### Theorem 5.4

$|V_{0}(f)|$-$\textsc{Extension Perfect Roman Domination}\in\textsf{W}[2]$.

###### Proof

For the membership, we only sketch the proof, as most parts are analogous to
the proof of Theorem 5.3. In this proof, we have $|V_{1}(f)|+1$ many tapes and
add the symbol $\\#$ to our work alphabet. On the first tape, the set
$V^{\prime}$ will be enumerated (as in proof of Theorem 5.3, so that
$V_{2}(f)\subseteq V^{\prime}$ and hopefully $V^{\prime}=V_{2}(g)$ for a
perfect rdf $g$ that extends $f$). Each remaining tape will represent a vertex
in $V_{1}(f)\coloneqq\\{u^{1},\dots,u^{\ell}\\}$. At the beginning,
$\ldots,b,\\#,b,\ldots$ is on each of these tapes and the head is on the
$b$-occurrence immediately to the right of $\\#$.

In the first $2i+1+2i^{2}$ ($i$ is the cardinality of $V^{\prime}$) steps, we
simulate the NTM of the proof of Theorem 5.3 on the first tape. The other
tapes stay the same. Hence, before we start the third phase, we know that the
first tape contains a list of vertices (without repetitions) that meet the
privacy condition. The third phase is different. We go once again through the
word on the first tape. Let $v_{j}^{j}$ for $j\in[i]$ be the symbol on the
current cell. Then proceed for the $(t+1)^{\text{st}}$ tape (for
$t\in[|V_{1}(f)|]$) as follows:

  * •

If $v^{j}=u^{t}$, then write two $\\#$ on the $(t+1)^{\text{st}}$ tape, moving
to the right after writing $\\#$.

  * •

If $v^{j}\in N_{G}(u^{t})$, then write one $\\#$ on the $(t+1)^{\text{st}}$
tape and go one step to the right.

  * •

If $v^{j}\notin N_{G}[u^{t}]$, then do nothing on the $(t+1)^{\text{st}}$
tape.

When we are gone through the first tape, we (blindly) move on each tape (but
the first tape) left twice. $b$ is now in a current cell of these tapes if and
only if the corresponding $u^{t}$ has exactly one neighbor in $V^{\prime}$ and
is not in $V^{\prime}$. So by 11, we go into the final state if and only if
each head is on a $\\#$.

Altogether, the described NTM would make at most $2i+1+2i^{2}+i+2$ many steps.
As $i=|V_{2}(g)|$, the claim follows with 11. ∎

For proving $\textsf{W}[2]$-hardness, we use $k$-Multicolored Dominating Set
which is known to be $\textsf{W}[2]$-complete, see [27].

Problem name: $k$-Multicolored Dominating Set
Given:  A graph $G=(V,E)$, $k\in\mathbb{N}$ and a partition
$W_{1},\ldots,W_{k}$ of $V$ Parameter:  $k$ Question:  Is there a dominating
set $D\subseteq V$ with $|W_{i}\cap D|=1$ for each $i\in[k]$?

###### Theorem 5.5

$|V_{0}(f)|$-Extension Perfect Roman Domination is $\textsf{W}[2]$-complete
even on bipartite graphs.

$\\{u_{1}\mid u\in N[v]\\}$$=$$v_{2}$$a$$b$⋮ (a) $v\in V$

$\\{u_{2}\mid u\in N[v]\\}$$=$$v_{1}$$x_{t}$⋮ (b) $t\in[k],v\in W_{t}$

Figure 2: Construction for Theorem 5.5

###### Proof

Let $G=(V,E)$ be a graph with the vertex set partition $W_{1},\ldots,W_{k}$.
Define $X\coloneqq\\{x_{1},\ldots,x_{k}\\}$ and
$\widetilde{G}=(\widetilde{V},\widetilde{E})$ with $a,b\notin V$,

$\begin{split}\widetilde{V}\coloneqq&\\{v_{1},v_{2}\mid v\in V\\}\cup
X\cup\\{a,b\\}\\\
\widetilde{E}\coloneqq&\\{\\{a,b\\}\\}\cup\\{\\{a,v_{2}\\}\mid v\in
V\\}\cup\\{\\{v_{1},x_{j}\\}\mid v\in W_{j}\\}\cup\\\
&\\{\\{v_{1},u_{2}\\}\mid v,u\in V,u\in N_{G}[v]\\}.\end{split}$

The graph is also visualized in Figure 2. $\widetilde{G}$ is bipartite with
two color classes $A\coloneqq V_{1}\cup\\{a\\}$ and $B\coloneqq X\cup
V_{2}\cup\\{b\\}$. To make it easier to verify for the reader, the vertices of
$A$ are mentioned first in the definition of $\widetilde{E}$. Further, define
$f:\widetilde{V}\to\\{0,1,2\\}$ with $V_{0}(f)\coloneqq
X\cup\\{b\\},\,V_{1}(f)\coloneqq\\{v_{1},v_{2}\mid v\in V\\}$ and
$V_{2}(f)\coloneqq\\{a\\}$. Clearly, this is even a polynomial-time reduction
and $|V_{0}(f)|=k+1$.

Let $D$ be a dominating set of $G$ with $|W_{i}\cap D|=1$ for each $i\in[k]$.
For $i\in[k]$, $u^{i}$ denotes the unique vertex in $W_{i}\cap D$. Define
$U=\\{u^{1}_{1},\ldots,u^{k}_{1}\\}\subseteq V_{1}$ and $g\in\\{0,1,2\\}^{V}$
such that $V_{0}(g)\coloneqq V_{0}(f)$, $V_{1}(g)\coloneqq V_{1}(f)\setminus
U$ and $V_{2}(g)\coloneqq\\{a\\}\cup U$.

By the use of 8, we will show that $g$ is a minimal perfect Roman dominating
function. First of all, $N_{G}(a)\cap V_{0}(g)=\\{b\\}$ and $N_{G}(b)\cap
V_{2}(g)=\\{a\\}$. Furthermore, for each $i\in[k]$, $N_{G}(u^{i}_{1})\cap
V_{0}(g)=\\{x_{i}\\}$ and $N_{G}(x_{i})\cap V_{2}(g)=\\{u^{i}_{1}\\}$. This
implies the first and last condition of 8. Let $v\in V$. If $v_{1}\in
V_{1}(g)$, then $N_{G}(v_{1})\cap V_{2}(g)=\emptyset$. As $D$ is a dominating
set, $D\cap N_{G}[v]$ is not empty. This implies that $|N_{G}(v_{2})\cap
V_{2}(g)|>1$. Thus, $g$ is a minimal perfect Roman dominating function.

Let $g\in\\{0,1,2\\}^{V}$ be a minimal perfect Roman dominating function on
$\widetilde{G}$ with $f\leq g$. Since $N_{G}(v_{2})\cap V_{0}(g)\subseteq
N_{G}(v_{2})\cap V_{0}(f)=\emptyset$ for all $v\in V$, $\\{v_{2}\mid v\in
V\\}\subseteq V_{1}(g)$. $V_{0}(f)\cap N_{G}(a)=\\{b\\}$ implies $g(b)=0$.
Define $W^{\prime}_{i}\coloneqq\\{v_{1}\mid v\in W_{i}\\}$ for $i\in[k]$. As
$N_{G}(w_{1})\cap V_{0}(f)=\\{x_{i}\\}$ holds for all $i\in[k]$ and $w_{1}\in
W^{\prime}_{i}$, $|V_{2}(g)\cap W_{i}|\leq 1$ for all $i\in[k]$. Define
$D\coloneqq\\{w\in V\mid\exists i\in[k]:\>\\{w_{1}\\}=V_{2}(g)\cap
W^{\prime}_{i}$. Hence, $|D\cap W_{i}|\leq 1$ for each $i\in[k]$. Let $v\in
V$. Since $g(v_{2})=1$ and $a\in N_{G}(v_{2})\cap V_{2}(g)$,
$N_{G}(v_{2})\cap(V_{2}(g)\setminus\\{a\\})$ is not empty.
$N_{G}(v_{2})\setminus\\{a\\}\subseteq\\{v_{1}\mid v\in V\\}$ implies
$N_{G}[v]\cap D^{\prime}\neq\emptyset$. Therefore, $D^{\prime}$ is a
dominating set. By adding an arbitrary vertex from $W_{i}$ with
$W^{\prime}_{i}\cap V_{2}(g)=\emptyset$ to $D^{\prime}$, we get a solution to
the Colored Dominating Set instance. ∎

##  6 Minimal Perfect Roman Domination and Minimal Roman Domination

In this section, we will take a look at the connection between minimal Roman
dominating functions and minimal perfect Roman dominating functions. To this
end, we will use the following theorem from [4].

###### Theorem 6.1

Let $G=\left(V,E\right)$ be a graph, $f:\>V\rightarrow\\{0,1,2\\}$ be a
function and let $G^{\prime}\coloneqq G\left[V_{0}\left(f\right)\cup
V_{2}\left(f\right)\right]$. Then, $f$ is a minimal Roman dominating function
if and only if the following conditions hold:

  1. 1.

$N_{G}\left[V_{2}\left(f\right)\right]\cap V_{1}\left(f\right)=\emptyset$,

  2. 2.

$\forall v\in
V_{2}\left(f\right):\>P_{G^{\prime},V_{2}\left(f\right)}\left(v\right)\nsubseteq\\{v\\}$,
and

  3. 3.

$V_{2}\left(f\right)$ is a minimal dominating set on $G^{\prime}$.

Let $G=(V,E)$ be graph. Define the sets of functions
$\mu-\mathcal{RDF}\left(G\right)=\\{f:V\to\\{0,1,2\\}\mid f$ is a minimal
Roman dominating function$\,\\}$ and
$\mu-\mathcal{PRDF}\left(G\right)=\\{f:V\to\\{0,1,2\\}\mid f$ is a minimal
perfect Roman dominating function$\,\\}$.

###### Theorem 6.2

Let $G=(V,E)$ be graph. There is a bijection
$B\colon\mu-\mathcal{RDF}\left(G\right)\to\mu-\mathcal{RDF}\left(G\right)$.
Furthermore, $B(f)$ and $B^{-1}(g)$ can be computed in polynomial time (with
respect to $G$) for each $f\in\mu-\mathcal{RDF}\left(G\right)$ and
$g\in\mu-\mathcal{PRDF}\left(G\right)$.

###### Proof

Let $f\in\mu-\mathcal{RDF}\left(G\right)$ and
$g\in\mu-\mathcal{PRDF}\left(G\right)$. Define $B(f)$ by the three sets

$\begin{split}V_{0}(B(f))=&\,\\{v\in V_{0}(f)\mid|N_{G}(v)\cap
V_{2}(f)|=1\\},\\\ V_{1}(B(f))=&\,\\{v\in V_{0}(f)\mid|N_{G}(v)\cap
V_{2}(f)|\geq 2\\}\cup V_{1}(f),\\\ V_{2}(B(f))=&\,V_{2}(f).\end{split}$

By definition of $B$, $|N_{G}(v)\cap V_{2}(f)|=1$ holds for all $v\in
V_{0}(B(f))$. Since each $v\in V$ with $f(v)=2$ needs a private neighbor
except itself by Theorem 6.1, $N_{G}(v)\cap V_{0}(B(f))\neq\emptyset$ holds.
As any $v\in V_{1}(f)$ has no neighbor in $V_{2}(f)$ and any $v\in
V_{1}(B(f))\setminus V_{1}(f)$ has at least two neighbors in $V_{2}(f)$, all
conditions of 8 are met. Therefore, $B(f)\in\mu-\mathcal{PRDF}\left(G\right)$.

Define $B^{-1}(g)$ by the three sets

$\begin{split}V_{0}(B^{-1}(g))=\,&V_{0}(g)\cup\\{v\in
V_{1}(g)\mid|N_{G}(v)\cap V_{2}(g)|\geq 2\\},\\\ V_{1}(B^{-1}(g))=\,&\\{v\in
V_{1}(g)\mid|N_{G}(v)\cap V_{2}(g)|=0\\},\\\
V_{2}(B^{-1}(g))=\,&V_{2}(f).\end{split}$

By definition of $B^{-1}$, $N_{G}(v)\cap V_{2}(B^{-1}(g))=\emptyset$ for each
$v\in V_{1}(B^{-1}(g))$. By 8, each $v\in V_{0}(g)$ has exactly one neighbor
in $V_{2}(g)$. Therefore, each vertex in $V_{0}(B^{-1}(g))$ has a neighbor in
$V_{2}(B^{-1}(g))$ and $V_{2}(B^{-1}(g))$ is a dominating set on
$G[V_{0}(B^{-1}(g))\cup V_{2}(B^{-1}(g))]$. 8 implies that each $v\in
V_{2}(g)$ has a $u\in N_{G}(v)\cap V_{0}(g)$ with $\\{v\\}=N_{G}(u)\cap
V_{2}(g)$. Hence, $u$ is a private neighbor of $v$ and
$B^{-1}(g)\in\mu-\mathcal{RDF}\left(G\right)$.

This leaves to show that $B^{-1}(B(f))=f$ and $B(B^{-1}(g))=g$. Trivially,
$V_{2}(B^{-1}(B(f)))=V_{2}(f)$ and $V_{2}(B(B^{-1}(g)))=V_{2}(g)$ hold. Let
$v\in V_{1}(f)$. By Theorem 6.1, we know $N_{G}(v)\cap V_{2}(f)=\emptyset$.
This implies $v\in V_{1}(B(f))\cap V_{1}(B^{-1}(B(f)))$. Let $v\in V_{0}(f)$
with $|N_{G}(v)\cap V_{2}(f)|=1$. Thus, $v\in V_{0}(B(f))\cap
V_{0}(B^{-1}(B(f)))$. Let $v\in V_{0}(f)$ with $|N_{G}(v)\cap V_{2}(f)|\geq
2$. Therefore, $v\in V_{1}(B(f))$ holds. The definition of $B^{-1}$ implies
$v\in V_{0}(B^{-1}(B(f)))$. Hence, $B^{-1}(B(f))=f$. Assume $v\in V_{0}(g)$. 8
implies $|N_{G}(v)\cap V_{2}(f)|=1$. Therefore, $v\in V_{0}(B(B^{-1}(f)))\cap
V_{0}(B^{-1}(f))$. For $v\in V_{1}(g)$ with $N_{G}(v)\cap V_{2}(g)=\emptyset$
the construction of the functions $B,B^{-1}$ implies $v\in
V_{1}(B(B^{-1}(f)))\cap V_{1}(B^{-1}(f))$. Let $v\in V_{1}(g)$ with
$|N_{G}(v)\cap V_{2}(g)|\geq 2$. This leads to $v\in V_{0}(B^{-1}(g))$ and
$v\in V_{1}(B(B^{-1}(g)))$. Hence, $B(B^{-1}(g))=g$. Therefore, the theorem
holds. ∎

This bijection is a so-called _parsimonious reduction_. This is a class of
reductions designed for enumeration problems. For more information, we refer
to [38]. Even without this paper, Theorem 6.2 implies some further results
thanks to [4].

###### Corollary 6

There are graphs of order $n$ that have at least
${\sqrt[5]{16}\,}^{n}\in\Omega(1.7441^{n})$ many minimal perfect rdf.

###### Theorem 6.3

There is a polynomial-space algorithm that enumerates all minimal perfect rdf
of a given graph of order $n$ with polynomial delay and in time
$\mathcal{O}^{*}(1.9332^{n})$.

According to [5], we get some further results for special graph classes: Let
$G=(V,E)$, with $n\coloneqq|V|$ being the order of $G$. If $G$ is a forest or
interval graph, then there is a perfect Roman dominating function enumeration
algorithm that runs in time $\mathcal{O}^{*}(\sqrt{3}^{n})$ with polynomial
delay. For both graph classes, a graph with many isolated edges is example of
a graph with $\sqrt{3}^{n}$ many minimal perfect Roman dominating function.
This is also the worst-case example for chordal graphs which is known so far.
We can enumerate all perfect Roman dominating functions of these graphs in
time $\mathcal{O}(1.8940^{n})$. If $G$ is a split or cobipartite graph, then
we can enumerate all perfect Roman dominating functions of $G$ in
$\mathcal{O}^{*}(\sqrt[3]{3}^{n})$ with polynomial delay. Further, both
classes include graphs of order $n$ with $\Omega(\sqrt[3]{3}^{n})$ many
perfect Roman dominating functions. There is also a polynomial-time recursive
algorithm to count all perfect Roman dominating functions of paths.

###### Remark 4

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ Figure 3: Counter-
example of 4

It should be mentioned that the function $B$ is inheriting the minimality but
it does not mean that if $f$ is a minimum Roman dominating function that
$B(f)$ is a minimum perfect Roman dominating function. For this we consider
the graph $G=(V,E)$ with $V\coloneqq\\{v_{1},\ldots,v_{8}\\}$ and

$E\coloneqq\\{\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\},\\{v_{4},v_{3}\\},\\{v_{5},v_{3}\\},\\{v_{4},v_{6}\\},\\{v_{5},v_{6}\\},\\{v_{7},v_{6}\\},\\{v_{8},v_{6}\\}\\}.$

Since $v_{1},v_{2}$ and $v_{7},v_{8}$ are pairs of false twins and
$v_{1},v_{7}$ have no common neighbors, for each Roman dominating function $f$
on $G$, $\omega\left(f\right)\geq 4$. Therefore, $f\in\\{0,1,2\\}^{V}$ with
$V_{0}(f)=\\{v_{1},v_{2},v_{4},v_{5},v_{7},v_{8}\\}$, $V_{1}(f)=\emptyset$ and
$V_{2}(f)=\\{v_{3},v_{6}\\}$ is a minimum Roman dominating function. $B(f)$ is
given by $V_{0}(B(f))=\\{v_{1},v_{2},v_{7},v_{8}\\}$,
$V_{1}(B(f))=\\{v_{4},v_{5}\\}$ and $V_{2}(f)=\\{v_{3},v_{6}\\}$. The weight
is $\omega\left(B(f)\right)=6$. The minimal perfect Roman dominating function
$g\in\\{0,1,2\\}$ with $V_{0}(g)=\\{v_{1},v_{2},v_{4},v_{5}\\}$,
$V_{1}(g)=\\{v_{6},v_{7},v_{8}\\}$ and $V_{2}(g)=\\{v_{3}\\}$ fulfills
$\omega\left(g\right)=5$. Hence, $B(f)$ is no minimum perfect Roman dominating
function.

Let $h\in\\{0,1,2\\}^{V}$ be minimal perfect Roman dominating function. For
$h(v_{3})=h(v_{6})=2$, $h=B(f)$, as $v_{1},v_{2},v_{7},v_{8}\in N(V_{2}(h))$
are pendant. Assume $h(v_{3})=2\neq h(v_{6})$. If $h(v_{4})=2$ (respectively
$h(v_{5})=2$), then $h(v_{7})=h(v_{8})=1$ and $\omega\left(h\right)\geq 6$.
For $h(v_{7})=2$ (respectively $h(v_{8})=2$), $h(v_{8})=1$ (respectively
$h(v_{7})=1$) and $\omega\left(g\right)=5\geq\omega\left(h\right)$. As
$v_{1},v_{2}\notin V_{2}(h)$ for $h(v_{3})=2$, the remaining possibility is
$h=g$. Thus, $\omega\left(g\right)=5\leq\omega\left(h\right)$ holds for each
minimal perfect Roman dominating function with $h(v_{3})=2\neq h(v_{6})$.
Analogously, for perfect Roman dominating functions $h$ with $h(v_{6})\neq
2=h(v_{3})$, $\omega\left(g\right)=5\leq\omega\left(h\right)$. Let
$h(v_{3})\neq 2$ and $h(v_{6})\neq 2$. Since
$N(v_{i})\subseteq\\{v_{3},v_{6}\\}$ for $i\in\\{1,2,4,5,7,8\\}$,
$v_{1},v_{2},v_{4},v_{5},v_{7},v_{8}\notin V_{0}(h)$. Hence,
$\omega\left(h\right)\geq 6$ and $g$ is a minimum perfect Roman dominating
function. Furthermore, $B^{-1}(g)=g$ is not a minimum Roman dominating
function.

##  7 Conclusion

We presented polynomial-time algorithms for Unique Response Roman Domination
on cobipartite and split graphs and one for Perfect Roman Domination on
cobipartite graphs. On split graphs, Perfect Roman Domination is NP-complete
but we provided an FPT-algorithm, parameterized by solution size. Then we gave
an $\mathcal{O}^{*}\left(\sqrt[3]{3}^{n}\right)$ enumeration algorithm for
unique response Roman dominating functions on graphs of order $n$ without
isolated vertices. This is an optimal algorithm as we also found a family of
graphs without isolated vertices of order $n$ and $\sqrt[3]{3}^{n}$ many
unique response Roman dominating functions. Although the extension version of
Perfect Roman Domination is NP-complete, proven to be even
$\textsf{W}[1]$-complete if parameterized by $\omega\left(f\right)$ and
$\textsf{W}[2]$-complete if parameterized by $|V_{0}(f)|$, we showed that all
perfect Roman dominating functions of a graph of order $n$ can be enumerated
in $\mathcal{O}^{*}(1.9332^{n})$ with polynomial delay. This is interesting,
as most often polyomial delay is linked to a polynomial-time decision
algorithm for the extension version of the corresponding property. The main
technique is to devise bijections to objects that can be enumerated with
polynomial delay, as (in our case) minimal Roman dominating functions. This
technique can be also applied to enumerate all minimal unique response strong
Roman dominating functions, as introduced in [32].

It could also be interesting to consider enumeration algorithms for other
variations of Roman domination functions such as double/connected/total Roman
dominating functions. In particular, it would be interesting to study under
which circumstances polynomial-delay enumeration is possible. Another
interesting research direction is to look into other graph classes which we
did not consider in this paper, now focusing on an input-sensitive analysis.
For example, we do not know of any enumeration algorithm for minimal Roman
dominating functions/perfect Roman dominating functions on bipartite graphs
which is better than the general one, although this class looks similar to the
ones of bipartite and split graphs where we could achieve considerable
improvements over the general case, see [5].

## References

  * [1] Abdollahzadeh Ahangar, H., Chellali, M., Sheikholeslami, S.M.: On the double Roman domination in graphs. Discrete Applied Mathematics 232, 1–7 (2017)
  * [2] Abdollahzadeh Ahangar, H., Henning, M.A., Samodivkin, V., Yero, I.G.: Total Roman domination in graphs. Applicable Analysis and Discrete Mathematics 10, 501–517 (2016)
  * [3] Abu-Khzam, F.N., Fernau, H., Mann, K.: Minimal Roman dominating functions: Extensions and enumeration. Tech. Rep. 2204.04765, Cornell University, ArXiv/CoRR (2022), https://doi.org/10.48550/arXiv.2204.04765
  * [4] Abu-Khzam, F.N., Fernau, H., Mann, K.: Minimal Roman dominating functions: Extensions and enumeration. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG. LNCS, vol. 13453, pp. 1–15. Springer (2022). https://doi.org/10.1007/978-3-031-15914-5_1
  * [5] Abu-Khzam, F.N., Fernau, H., Mann, K.: Roman census: Enumerating and counting Roman dominating functions on graph classes. In: Leroux, J., Lombardy, S., Peleg, D. (eds.) 48th International Symposium on Mathematical Foundations of Computer Science, MFCS. Leibniz International Proceedings in Informatics (LIPIcs), vol. 272, pp. 6:1–6:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
  * [6] Banerjee, S., Chaudhary, J., Pradhan, D.: Unique response Roman domination: Complexity and algorithms. Algorithmica p. to appear (2023). https://doi.org/10.1007/s00453-023-01171-7
  * [7] Banerjee, S., Henning, M.A., Pradhan, D.: Algorithmic results on double Roman domination in graphs. Journal of Combinatorial Optimization 39(1), 90–114 (2020)
  * [8] Banerjee, S., Keil, J.M., Pradhan, D.: Perfect Roman domination in graphs. Theoretical Computer Science 796, 1–21 (2019)
  * [9] Beeler, R.A., Haynes, T.W., Hedetniemi, S.T.: Double Roman domination. Discrete Applied Mathematics 211, 23–29 (2016)
  * [10] Benecke, S.: Higher Order Domination of Graphs. Master’s thesis, Department of Applied Mathematics of the University of Stellebosch, South Africa, http://dip.sun.ac.za/~vuuren/Theses/Benecke.pdf (2004)
  * [11] Cabrera Martínez, A., Puertas, M., Rodríguez-Velázquez, J.: On the 2-packing differential of a graph. Results in Mathematics 76, 175:1–175:24 (2021)
  * [12] Casel, K., Fernau, H., Ghadikolaei, M.K., Monnot, J., Sikora, F.: Abundant extensions. In: Calamoneri, T., Corò, F. (eds.) Algorithms and Complexity - 12th International Conference, CIAC. LNCS, vol. 12701, pp. 3–17. Springer (2021). https://doi.org/10.1007/978-3-030-75242-2_1
  * [13] Cattanéo, D., Perdrix, S.: The parameterized complexity of domination-type problems and application to linear codes. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) Theory and Applications of Models of Computation, TAMC. LNCS, vol. 8402, pp. 86–103. Springer (2014)
  * [14] Chapelle, M., Cochefert, M., Couturier, J., Kratsch, D., Liedloff, M., Perez, A.: Exact algorithms for weak Roman domination. In: Lecroq, T., Mouchard, L. (eds.) Combinatorial Algorithms - 24th International Workshop, IWOCA. LNCS, vol. 8288, pp. 81–93. Springer (2013)
  * [15] Chellali, M., Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., McRae, A.A.: A Roman domination chain. Graphs and Combinatorics 32(1), 79–92 (2016)
  * [16] Chellali, M., Haynes, T.W., Hedetniemi, S.T., McRae, A.A.: Roman {2}-domination. Discrete Applied Mathematics 204, 22–28 (2016)
  * [17] Downey, R.G., Fellows, M.R., Raman, V.: The complexity of irredundant set parameterized by size. Discrete Applied Mathematics 100, 155–167 (2000)
  * [18] Dreyer, P.A.: Applications and Variations of Domination in Graphs. Ph.D. thesis, Rutgers University, New Jersey, USA (2000)
  * [19] Fellows, M.R., Hoover, M.N.: Perfect domination. Australasian Journal of Combinatorics 3, 141–150 (1991)
  * [20] Fernau, H.: Roman Domination: a parameterized perspective. International Journal of Computer Mathematics 85, 25–38 (2008)
  * [21] Fernau, H., Golovach, P.A., Sagot, M.: Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). Dagstuhl Reports 8(10), 63–86 (2018)
  * [22] Fernau, H., Mann, K.: Hitting the Romans. Tech. Rep. abs/2302.11417, Cornell University, ArXiv/CoRR (2023). https://doi.org/10.48550/arXiv.2302.11417
  * [23] Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 1–17 (2008)
  * [24] Henning, M.A., Klostermeyer, W.F., MacGillivray, G.: Perfect Roman domination in trees. Discrete Applied Mathematics 236, 235–245 (2018)
  * [25] Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Information Processing Letters 27(3), 119–123 (1988)
  * [26] Junosza-Szaniawski, K., Rzążewski, P.: On the number of 2-packings in a connected graph. Discrete Mathematics 312, 3444–3450 (2012)
  * [27] Lackner, M., Pfandler, A.: Fixed-parameter algorithms for finding minimal models. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR. AAAI Press (2012)
  * [28] Liedloff, M.: Algorithmes exacts et exponentiels pour les problèmes NP-difficiles: domination, variantes et généralisations. PhD thesis, Université Paul Verlaine - Metz, France (2007)
  * [29] Liedloff, M., Kloks, T., Liu, J., Peng, S.L.: Efficient algorithms for Roman domination on some classes of graphs. Discrete Applied Mathematics 156(18), 3400–3415 (2008)
  * [30] Liu, C.H., Chang, G.J.: Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization 26(3), 608–619 (2013)
  * [31] Marino, A.: Analysis and enumeration. Algorithms for biological graphs, Atlantis Studies in Computing, vol. 6. Atlantis Press, Paris (2015)
  * [32] Mojdeh, D.A., Hao, G., Masoumi, I., Parsian, A.: Unique response strong Roman dominating functions of graphs. Electronic Journal of Graph Theory and Applications 9, 469–484 (2021)
  * [33] Pagourtzis, A., Penna, P., Schlude, K., Steinhöfel, K., Taylor, D.S., Widmayer, P.: Server placements, Roman domination and other dominating set variants. In: Baeza-Yates, R.A., Montanari, U., Santoro, N. (eds.) Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17${}^{\mbox{th}}$ World Computer Congress — TC1 Stream / 2${}^{\mbox{nd}}$ IFIP International Conference on Theoretical Computer Science IFIP TCS. pp. 280–291. Kluwer (2002), also available as Technical Report 365, ETH Zürich, Institute of Theoretical Computer Science, 10/2001.
  * [34] Peng, S.L., Tsai, Y.H.: Roman domination on graphs of bounded treewidth. In: The 24th Workshop on Combinatorial Mathematics and Computation Theory. pp. 128–131 (2007)
  * [35] Rubalcaba, R.R., Slater, P.J.: Roman dominating influence parameters. Discrete Mathematics 307(24), 3194–3200 (2007)
  * [36] Schirneck, M.: Enumeration algorithms in data profiling. Ph.D. thesis, University of Potsdam, Germany (2022), https://publishup.uni-potsdam.de/frontdoor/index/index/docId/55672
  * [37] Shang, W., Wang, X., Hu, X.: Roman domination and its variants in unit disk graphs. Discrete Mathematics, Algorithms and Applications 2(1), 99–106 (2010)
  * [38] Strozecki, Y.: Enumeration complexity. EATCS Bulletin 129 (2019)
  * [39] Targhi, E.E., Rad, N.J., Volkmann, L.: Unique response Roman domination in graphs. Discrete Applied Mathematics 159(11), 1110–1117 (2011)
  * [40] Wasa, K.: Enumeration of enumeration algorithms. Tech. Rep. 1605.05102, Archiv, Cornell University (2016)