Universität Trier, Fachbereich IV, Informatikwissenschaften, Germany and
https://www.uni-trier.de/index.php?id=49861<EMAIL_ADDRESS>https://orcid.org/0000-0002-4444-3220 Universität Trier, Fachbereich IV,
Informatikwissenschaften, Germany<EMAIL_ADDRESS>https://orcid.org/0000-0002-0880-2513 Henning Fernau and Kevin Mann <ccs2012>
<concept> <concept_id>10003752.10003777.10003779</concept_id>
<concept_desc>Theory of computation Problems, reductions and
completeness</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept> <concept_id>10003752.10003809.10010052</concept_id>
<concept_desc>Theory of computation Parameterized complexity and exact
algorithms</concept_desc> <concept_significance>500</concept_significance>
</concept> </ccs2012> [500]Theory of computation Problems, reductions and
completeness [500]Theory of computation Parameterized complexity and exact
algorithms 1

# Hitting the Romans

Henning Fernau  Kevin Mann

###### Abstract

Roman domination is one of few examples where the related extension problem is
polynomial-time solvable even if the original decision problem is NP-complete.
This is interesting, as it allows to establish polynomial-delay enumeration
algorithms for finding minimal Roman dominating functions, while it is open
for more than four decades if all minimal dominating sets of a graph or if all
hitting sets of a hypergraph can be enumerated with polynomial delay. To find
the reason why this is the case, we combine the idea of hitting set with the
idea of Roman domination. We hence obtain and study two new problems, called
Roman Hitting Function and Roman Hitting Set, both generalizing Roman
Domination. This allows us to delineate the borderline of polynomial-delay
enumerability. Here, we assume what we call the _Hitting Set Transversal
Thesis_ , claiming that it is impossible to enumerate all minimal hitting sets
of a hypergraph with polynomial delay. Our first focus is on the extension
versions of these problems. While doing this, we find some conditions under
which the Extension Roman Hitting Function problem is NP-complete. We then use
parameterized complexity to get a better understanding of why Extension Roman
Hitting Function behaves in this way. Furthermore, we analyze the
parameterized and approximation complexity of the underlying optimization
problems. We also discuss consequences for Roman variants of other problems
like Vertex Cover.

###### keywords:

enumeration problems, polynomial delay, domination problems, hitting set,
Roman domination

###### category:

##  1 Introduction

Defense strategies in the Roman Empire have been studied throughout the
centuries, mostly from a historical-military perspective, but then also from a
more graph-theoretic viewpoint, commencing with an article by
Arquilla111Arquilla is quite known for his analysis of cyberwar, see
[Arq2011]. and Fredricksen [ArqFre95]. The strategy that we are also
discussing in this paper is nowadays known as Roman domination and was
introduced in [Ste99] in line with the discussions of Arquilla and
Fredricksen, formalizing a military strategic decision going back to
Constantine the Great.

The concept of Roman domination is a well-studied variation of domination in
graphs, certified by its own 45-page chapter in the relatively recent textbook
[HayHedHen2020], written by Chellali _et al._ Here, armies are placed in
different regions. A region is secured if there is at least one army in this
region or there are two armies in one neighbored region. Mathematically, we
model the map as a graph, where regions correspond to vertices and connections
between regions correspond to edges; moreover, the placement of armies is
described by a function which maps each vertex to 0, 1 or 2. Such a function
is called _Roman dominating_ if each vertex with value 0 has a neighbor with
value 2. It is clearly desirable to minimize expenses by finding a Roman
dominating function that uses the least number of armies; the corresponding
decision problem is called Roman Domination.

Apart from quite a number of combinatorial (graph-theoretic) results that have
been obtained for Roman domination, nicely surveyed in [HayHedHen2020], the
decision problem Roman Domination has been studied from various aspects.
Roughly speaking, Roman Domination behaves quite similarly to the classical
and well-known Dominating Set problem. More specifically, to mention some of
these results:

  * •

Roman Domination is NP-complete, even on special graph classes; see
[Dre2000a]. A simpler proof is shown in [Pagetal2002], from which it is also
clear (though not stated there) that subexponential-time algorithms can be
excluded assuming ETH (Exponential Time Hypothesis).

  * •

Minimum Roman Domination can be approximated up to a logarithmic factor but
not any better, unless $\textsf{P}=\textsf{NP}$, confer [Pagetal2002] and also
[PadPal2020].

  * •

Roman Domination under standard parameterization (by an upper-bound $k$ on the
number of armies) is complete for $\textsf{W}[2]$; see [Fer08]. However, the
dual parameterization puts Roman Domination in FPT; this is explicit in
[AbuBCF2016] and can be also obtained by combining [BerFer2015] with
[BerFerSig2014].

Even though Roman Domination and Dominating Set behave the same in terms of
complexity in a variety of settings, this parallelism possibly surprisingly
breaks down for two (mutually related) tasks:

  * •

Can we enumerate all minimal solutions of a given instance with polynomial
delay?

  * •

Can we decide, given a certain part of the solution, if there exists a minimal
solution that extends the given pre-solution?

The first type of question is also known as an _output-sensitive enumeration_
problem. It is an open question since four decades if there exists an
algorithm that enumerates all inclusion-wise minimal dominating sets with
polynomial delay only, i.e., a user has to wait only polynomial time until the
first minimal dominating set is shown, and also between any two outputs, and
also between the last output solution and the termination of the algorithm.
The corresponding enumeration question for Roman dominating functions (for two
natural notions of minimality) can be solved with polynomial delay, as proven
in [AbuFerMan2022b]. This result on Roman domination is based on another
result giving a polynomial-time algorithm for the _extension problem(s)_ as
described in the second item. Namely, the idea is to call an extension test
before diving further into branching. This strategy is well-established in the
area of enumeration algorithms, but few concrete examples are known; we only
refer to the discussion in [Str2019]. This makes Extension Roman Domination
one of few examples where the extension problem is polynomial-time solvable,
while the original problem is NP-complete. For more details on extension
problems, we refer to the survey [CasFGMS2022] that also suggests a general
framework to describe such problems and provides further motivations and
applications.

The simple scientific question that we want to investigate in this paper is
“why”: _What causes Roman domination to be feasible with respect to
enumeration and extension?_ To find out why Extension Roman Domination behaves
in this peculiar way and what can be seen as a difference to Extension
Dominating Set, we want to generalize the concept of Roman domination and try
to find the borderline of tractability. By this, we refer to the question if
minimal hitting sets can be enumerated with polynomial delay. This so-called
_Hitting Set Transversal Problem_ is open for four decades. It is possibly
time to put it up in the form of a conjecture: The _Hitting Set Transversal
Thesis_ (or HSTT for short) would claim that there is no polynomial-delay
enumeration algorithm for minimal hitting sets. This question is equivalent to
several enumeration problems in logic, database theory and also to enumerating
minimal dominating sets in graphs, see [CreKPSV2019, EitGot95, GaiVer2017,
KanLMN2014]. Our paper can be read as trying to understand for which problems
polynomial-delay enumeration is not possible, assuming HSTT, and furthermore,
to describe situations when polynomial-delay enumeration algorithms exist.
Previous research on enumeration algorithms for minimal dominating sets often
tried to look into special graph classes where polynomial-delay enumeration
could be exhibited, or not, assuming HSTT. For instance, in [KanLMN2014] it is
shown that minimal dominating sets can be enumerated with polynomial delay in
split graphs,222Kanté _et al._ use a direct argument for this polynomial delay
enumeration result. It can be also shown that the extension problem to minimal
dominating sets is solvable in polynomial time in split graphs. while minimal
connected dominating sets cannot, assuming HSTT, also see [KanLMN2011]. In
fact, it is shown in [KanLMN2014] that several graph enumeration problems are
equivalent to enumerating minimal hitting sets when it comes to the question
of polynomial delay. This approach can be seen as specializing a known (HSTT-
hard) enumeration problem by studying special graph classes. Our approach is
different, as we come from a domination-type problem with a known polynomial-
delay enumeration algorithm for general graphs and we try to stretch this
result by generalization to understand when this enumeration task becomes
infeasible, assuming HSTT.

It is well-known that Hitting Set can be viewed as a generalization of
Dominating Set by modelling a graph by the closed-neighborhood hypergraph.
Although Hitting Set and Roman Domination are both established concepts that
generalize Dominating Set, it seems that there is no combination of both
concepts published in the literature. Actually, trying to define such a
combination comes with some problems. If we want a Hitting set instance to
represent a Dominating Set instance, the vertex set of the given graph is the
vertex set of the hypergraph that we have to construct, also known as the
“universe”, and the set of all closed neighborhoods is the (hyper)edge set.
Ignoring twins, this implies a bijection between the universe and the
(hyper)edge set. But in general hypergraphs, the number of hyperedges and the
number of elements in the universe does not necessarily have to be the same.
Therefore, we have to think about how to interpret the “value one setting”
such that it is related to the definition of Roman Domination where exactly
one army is put on a certain vertex. We suggest two ways of modelling this
effect in hypergraphs:

  1. 1.

If a vertex has the value one under a Roman dominating function, then it hits
only its own closed-neighborhood hyperedge.

  2. 2.

If a vertex has the value one under a Roman dominating function, then its
closed neighborhood needs _not_ be hit by some incident vertex with value 2.

Following the first interpretation, we need a function, called
_correspondence_ , which maps a vertex to an incident hyperedge, such that
this hyperedge is dominated if the vertex has the value 1. We will call the
related decision problem Roman Hitting Function. The second interpretation
implies that the value 1 is related to a hyperedge rather than to its incident
vertex. The related decision problem will be called Roman Hitting Set. We will
use these ideas to define these two different hypergraph problems more
formally in the next section. Moreover, we briefly discuss the notion of
domination in hypergraphs that has been introduced before in the literature.

To wrap up our main results quickly: Roman Hitting Set leads to a
generalization of Roman Domination whose extension version is polynomial-time
solvable and hence, minimal Roman hitting sets can be enumerated with
polynomial delay. However, for Roman Hitting Function, it seems to be crucial
whether or not the correspondence is surjective. If it is surjective, then we
can prove that the extension version of Roman Hitting Function is again
polynomial-time solvable and hence, under this condition minimal Roman hitting
functions can be enumerated with polynomial delay. If this surjectivity
condition is not met, then the extension version of Roman Hitting Function is
NP-complete, and various attempts to parameterize this problem also fail and
do not lead to FPT-delay enumeration algorithms. This way, we obtain a clear
borderline of feasibility for enumerating minimal Roman hitting functions. We
also show how to define notions like Roman vertex cover and transfer
polynomial-delay enumeration results.

##  2 Definitions and Notation

Throughout this paper, we will freely use standard notions from complexity
theory without defining them here. This includes notions from parameterized
complexity, concerning FPT and the further lower levels of the W-hierarchy up
to $\textsf{W}[3]$, as described in textbooks like [FluGro2006, DowFel2013].

###  2.1 General Notions, Graphs and Hypergraphs

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\\}$. For
a finite set $A$ and some $n\in\mathbb{N}$ with $n\leq|A|$, the cardinality of
$A$, $\binom{A}{n}$ denotes the set of all subsets of $A$ of cardinality $n$,
while $2^{A}$ denotes the power set of $A$. For two sets $A,B$, $B^{A}$
denotes the set of all mappings $f:A\rightarrow B$. If $C\subseteq A$, then
$f(C)=\\{f(x)\mid x\in C\\}\subseteq B$. We denote by
$\chi_{C}\in\\{0,1\\}^{A}$ the characteristic function, where $\chi_{C}(x)=1$
holds if and only if $x\in C$. For two functions $f,g\in\mathbb{N}^{A}$, we
write $f\leq g$ if and only if $f(a)\leq g(a)$ holds for all $a\in A$.
Further, we define the _weight_ of $f$ by $\omega\left(f\right)=\sum_{a\in
A}f(a)$.

We focus on hypergraphs $H=\left(X,\hat{S}=\left(s_{i}\right)_{i\in I}\right)$
with a finite universe $X$, also called _vertex_ set, and a finite index set
$I$, where for each $i\in I$, $s_{i}\subseteq X$ is a _hyperedge_. With the
set $S$ we denote the set which includes all hyperedges of the sequence
$\hat{S}$, i.e., $S=\\{s_{i}\mid{i\in I}\\}$. Note that that the same
hyperedge may appear multiple times in the sequence $\hat{S}$. If this is
forbidden, we speak of a _simple_ hypergraph. For all $x\in X$, define
$\mathbf{S}(x)=\\{s_{i}\in S\mid x\in s_{i}\\}$ as the set of hyperedges that
is _hit_ by the vertex $x$, hence defining a function $\mathbf{S}:X\to 2^{S}$.
A set $D\subseteq X$ is a _hitting set_ if and only if $\mathbf{S}(D)=S$,
where $\mathbf{S}(D)=\bigcup_{x\in D}\mathbf{S}(x)$. Similarly, define
$\mathbf{I}:X\to 2^{I}$ by $\mathbf{I}(x)=\\{i\in I\mid x\in s_{i}\\}$,
exentending to $A\subseteq X$ by $\mathbf{I}(A)=\bigcup_{x\in
A}\mathbf{I}(x)$. We call a function $\tau:X\rightarrow I$ a _correspondence_
if $x\in s_{\tau(x)}$ for all $x\in X$ or if, in other words,
$\tau(x)\in\mathbf{I}(x)$ for all $x\in X$.

We can consider a (simple undirected) graph $G=(V,E)$ as a hypergraph
$G=(V,\hat{E})$, where each hyperedge contains exactly two elements. In this
case, we call the hyperedges just edges. Talking about simple graphs, we can
consider $E$ as the index set. For each vertex $v\in V$, define its
neighborhood as $N(v)=\\{u\mid\\{v,u\\}\in E\\}$ and the closed neighborhood
as $N[v]=\\{v\\}\cup N(v)$. For vertex sets $U\subseteq V$, we use
$N[U]=\bigcup_{v\in U}N[v]$ for the closed neighborhood of $U$. A _dominating
set_ of a graph $G=(V,E)$ is a set $D\subseteq V$ such that $N[D]=V$.

###  2.2 Roman Dominating Functions

Let $G=(V,{E})$ be a graph. A function $f\in\\{0,1,2\\}^{V}$ is a _Roman
dominating function_ (rdf for short) if and only if, for each vertex $v\in V$
with $f(v)=0$, there exists a $u\in N(v)$ with $f(u)=2$. For
$f,g\in\\{0,1,2\\}^{V}$, define $f\leq_{PO}g$ if and only if $f(v)=0$ or
$f(v)=g(v)$ for each $v\in V$. A Roman dominating function $f$ is minimal (or
PO-minimal, respectively) if for each Roman dominating function $g$ with
$g\leq f$ (or $g\leq_{PO}f$, respectively), $f=g$ holds. We will consider the
following problems.

Problem name: Roman Domination, or RD for short Given:  A graph $G=(V,{E})$
and $k\in\mathbb{N}$ Question:  Is there a rdf $f$ with
$\omega\left(f\right)\leq k$?

Problem name: (PO-)Extension Roman Domination, or (PO-)Ext RD for short.
Given:  A graph $G=(V,{E})$ and a function $f:V\to\\{0,1,2\\}$ Question:  Is
there a minimal rdf $g$ for $G$ with $f\leq_{(PO)}g$?

Somewhat surprisingly, the extension problems in the second box were proven to
be polynomial-time solvable in [AbuFerMan2022b]. This implies that
(PO-)minimal rdf can be enumerated with polynomial delay. In order to explore
why these results were possible, we are going to generalize these notions and
problems for hypergraphs in three ways.

The first one is probably the most natural one, formed in analogy to the
notion of a dominating set in a (simple) hypergraph; see [Ach2007]. Let
$H=(V,E)$ be a (simple) hypergraph, i.e., $E\subseteq 2^{V}$. Then,
$f:V\to\\{0,1,2\\}$ is a Roman dominating function if, for all $v\in V$ with
$f(v)=0$, there is a vertex $u\in V$ with $f(v)=2$ that is a neighbor of $v$,
i.e., it shares an edge with $v$, which means, more formally, that there
exists some $e\in E$ with $\\{u,v\\}\subseteq e$. The problems can then be
defined as for graphs. We will call them Hypergraph Roman Domination, or HRD
for short, and (PO-)Extension Hypergraph Roman Domination, or (PO-)Ext HRD for
short.

However, as we show next, we can transfer all interesting properties of Roman
domination from the graph case to the hypergraph setting, basically by using
the same reduction. More specifically, we can show:

######  Proposition 2.1.

HRD is NP-complete.

######  Proposition 2.2.

(PO-)Ext HRD can be solved in polynomial time.

######  Proposition 2.3.

One can enumerate all (PO-)minimal Roman dominating function of a hypergraph
with polynomial delay.

Namely, if $G=(V,E)$ is a simple hypergraph, we can construct a graph
$G^{\prime}=(V,E^{\prime})$ by setting $\\{x,y\\}\in E^{\prime}$ if and only
if there is a hyperedge $e\in E$ with $\\{x,y\\}\subseteq e$. Then,
$f:V\to\\{0,1,2\\}$ is a Roman dominating function of the hypergraph $G$ if
and only if $f$ is a Roman dominating function of the graph $G^{\prime}$.
Conversely, we just have to interpret a given graph as a simple hypergraph.

Therefore, we propose two further generalizations of Roman domination towards
hypergraphs that allow us to study why Roman domination shows such a peculiar
behavior when it comes to its extension version, as well as concerning
enumerating minimal Roman dominating functions. These definitions can be found
in the next subsections.

The basis of the polynomial-delay enumeration algorithm is a combinatorial
characterization of minimal Roman dominating functions. To be able to
formulate the mentioned combinatorial characterization of minimal rdf, we need
a further notion. For $D\subseteq V$ and $v\in D$, define the _private
neighborhood_ of $v\in V$ with respect to $D$ as
$P_{G,D}\left(v\right)\coloneqq N_{G}\left[v\right]\setminus
N_{G}\left[D\setminus\\{v\\}\right]$. The vertices in $P_{G,D}\left(v\right)$
are called private neighbors of $v$.

######  Theorem 2.4.

[AbuFerMan2022b] Let $G=\left(V,E\right)$ be a graph and $f:\>V\to\\{0,1,2\\}$
be a function. Abbreviate $G^{\prime}\coloneqq G\left[f^{-1}(0)\cup
f^{-1}(2)\right]$. Then, $f$ is a minimal rdf if and only if the following
constraints hold:

  1. 1.

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

  2. 2.

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

  3. 3.

$f^{-1}(2)$ is a minimal dominating set of $G^{\prime}$.

######  Theorem 2.5.

[AbuFerMan2022b] Let $G=\left(V,E\right)$ be a graph and $f:\>V\to\\{0,1,2\\}$
be a function. Abbreviate $G^{\prime}\coloneqq G\left[f^{-1}(0)\cup
f^{-1}(2)\right]$. Then, $f$ is a PO-minimal rdf if and only if the following
constraints hold:

  1. 1.

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

  2. 2.

$f^{-1}(2)$ is a minimal dominating set of $G^{\prime}$.

###  2.3 Roman Hitting Functions

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph and $\tau:X\rightarrow I$
be a correspondence. We call a function $f\in\\{0,1,2\\}^{X}$ a _Roman hitting
function_ (rhf for short) if, for each $i\in I$, there exists an $x\in s_{i}$
with $f(x)=2$ or if there exists an $x\in X$ with $\tau(x)=i$ and $f(x)=1$. In
these scenarios, we say that $x$ hits $i$ or $s_{i}$. For a function
$f\in\\{0,1,2\\}^{X}$, we define the partition
$P(f)=\\{f^{-1}(0),f^{-1}(1),f^{-1}(2)\\}$. We now define two decision
problems related to rhf.

Problem name: Roman Hitting Function, or RHF for short Given:  A finite set
$X$, a hyperedge sequence $\hat{S}=\left(s_{i}\right)_{i\in I}$, forming the
hypergraph $(X,\hat{S})$, a correspondence $\tau:X\to I$, and $k\in\mathbb{N}$
Question:  Is there a rhf $f$ with $\omega\left(f\right)\leq k$?

Problem name: Extension Roman Hitting Function, or Ext RHF for short Given:  A
finite set $X$, a hyperedge sequence $\hat{S}=\left(s_{i}\right)_{i\in I}$,
forming the hypergraph $(X,\hat{S})$, a correspondence $\tau:X\to I$, and
$f:X\to\\{0,1,2\\}$ Question:  Is there a minimal rhf $g$ with $f\leq g$?

To understand in which way this setting generalizes RD, recall that there are
alternative ways to specify a graph as a hypergraph. More precisely, the
_closed-neighborhood hypergraph_ $G_{nb}$ associated to a graph $G=(V,E)$ can
be described as $G_{nb}=(V,(N[v])_{v\in V})$. Clearly, $D\subseteq V$ is a
dominating set if and only if $D$ is a hitting set of $G_{nb}$. As $v\in
N[v]$, the identity can be viewed as a correspondence. In this interpretation,
$f:V\to\\{0,1,2\\}$ is a Roman domination function of $G$ if and only if it is
a Roman hitting function of $G_{nb}$.

###  2.4 Roman Hitting Sets

Let $(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph. We call
$R=\left(R_{1},R_{2}\right)\in 2^{I}\times 2^{X}$ a _Roman hitting set_ , or
rhs for short, if and only if, for all $i\in I$, $s_{i}\cap
R_{2}\neq\emptyset$ or $i\in R_{1}$. If $x\in s_{i}\cap R_{2}$ we say $x$
_hits_ $i$ or $s_{i}$. In the case that $i\in R_{1}$ we say $i$ _hits itself_.
For two tuples $(P_{1},P_{2}),(R_{1},R_{2})\in 2^{I}\times 2^{X}$ we say
$(P_{1},P_{2})\leq(R_{1},R_{2})$ if $P_{1}\subseteq R_{1}$ and $P_{2}\subseteq
R_{2}$. We call a rhs $P$ _minimal_ if $R\leq P$ implies $R=P$ for each rhs
$R$. Adapting earlier notations, we also write
$\omega(R_{1},R_{2})\coloneqq|R_{1}|+2\cdot|R_{2}|$, calling it the _weight_
of $(R_{1},R_{2})\leq(I,X)$.

######  Example 2.6.

Consider some $f:V\to\\{0,1,2\\}$. Then, $f$ is a rhf if and only if
$(\tau(f^{-1}(1)),f^{-1}(2))$ is a rhs, but for $X=\\{a,b,c,d\\}$ and
$\hat{S}\coloneqq(s_{1}\coloneqq\\{a,b\\},s_{2}\coloneqq\\{a\\},s_{3}\coloneqq\\{b\\},s_{4}\coloneqq\\{a,c\\},s_{5}\coloneqq\\{c,d\\})$,
$I\coloneqq[5]$, $R_{1}=[3]$ and $R_{2}=\\{c\\}$ forms a valid rhs that does
not correspond to any rhf for the hypergraph $(X,\hat{S})$.

######  Lemma 2.7.

Let $H=(V,(s_{i})_{i\in I})$ be a hypergraph and $\tau:V\to I$ be a
correspondence. $\tau$ is surjective if and only if for each rhs
$(R_{1},R_{2})$ of $h$ there exists a rhf $f:V\to\\{0,1,2\\}$ with
$f^{-1}(2)=R_{2}$.

######  Proof 2.8.

Let $H=(V,(s_{i})_{i\in I})$ be a hypergraph and let $\tau:V\to I$ be a
correspondence. Furthermore, let $\tau$ be surjective and let $(R_{1},R_{2})$
be a rhs. Then $f:V\to\\{0,1,2\\}$ is a rhf, where $f$ is defined as $f(v)=2$
if $v\in R_{2}$ and $f(v)=1$ if $v\in\phi(\tau^{-1}(i))$ for some $i\in
R_{1}$, where $\phi$ is Zermelo’s choice function, and $f(v)=0$, otherwise.

Assume $\tau$ is not surjective. Then there is an $i\in I$ with
$\tau^{-1}(i)=\emptyset$. $(I,\emptyset)$ is a rhs, but there is no rhf with
$f^{-1}(2)=\emptyset$, as for all $j\in I$ there has to be a $v\in
f{-1}(1)\cap\tau^{-1}(j)$. This is not the case for $j=i$.

In particular, if we consider functions $f:V\to\\{0,1,2\\}$ associated to a
graph $G=(V,E)$, then $f$ is a rdf if and only if, in the related hypergraph
$G_{nb}$, $f$ is a rhf if and only if $(f^{-1}(1),f^{-1}(2))$ is a rhs in
$G_{nb}$, as we view the identity as our correspondance. In that case,
$\omega\left(f\right)=\omega(f^{-1}(1),f^{-1}(2))$. As a further example,
consider $X=\\{a,b,c,d\\}$ and
$\hat{S}\coloneqq(s_{1}\coloneqq\\{a,b\\},s_{2}\coloneqq\\{b,c\\},s_{3}\coloneqq\\{b,e\\},s_{4}\coloneqq\\{b,c,d\\},s_{5}\coloneqq\\{d,e\\})$,
$I\coloneqq[5]$. If the correspondence $\tau$ that we are considering
satisfies $\tau(d)=s_{4}$ and $\tau(e)=s_{3}$, then $\tau$ cannot be
surjective, as $s_{5}\notin\tau(X)$. A rhs with smallest weight 3 is
$(\\{s_{5}\\},\\{b\\})$. However, any rhf $f$ for $(X,\hat{S})$ that respects
$\tau$ must have $f(d)=2$ or $f(e)=2$. In either case, for the remaining
hypergraph, at least weight 2 is needed, so that $\omega(f)\geq 4$ is
enforced.

The concept of rhs gives rise to two decision problems:

Problem name: Roman Hitting Set, or RHS for short Given:  A hypergraph
$H=(X,\hat{S}=\left(s_{i}\right)_{i\in I})$ and $k\in\mathbb{N}$ Question:  Is
there a rhs $(R_{1},R_{2})$ of $H$ with $\omega(R_{1},R_{2})\leq k$?

Problem name: Extension Roman Hitting Set, or Ext RHS for short Given:  A
hypergraph $H=(X,\hat{S}=\left(s_{i}\right)_{i\in I})$ and some
$U=(U_{1},U_{2})\leq(I,X)$ Question:  Is there a minimal rhs
$R=({R_{1}},R_{2})$ of $H$ with $U\leq R$?

More precisely, if $G=(V,E)$ is a graph, then take $X=V$,
$\hat{S}_{G}=(N[v])_{v\in V}$, defining the closed-neighborhood hypergraph
$G_{nb}$. In this case, a function $f$ is a rdf if and only if
$(f^{-1}(1),f^{-1}(2))$ is a rhs. Hence, $(G,k)$ is a yes-instance of Roman
Domination if and only if $(X,\hat{S}_{G},k)$ is a yes-instance of RHF. For
the if-part, we have to show that if there exists a rhs $(R_{1},R_{2})$ with
$|R_{1}|+2\cdot|R_{2}|\leq k$ then there exists a rhs $(P_{1},P_{2})$ with
$|P_{1}|+2\cdot|P_{2}|\leq k$ and $P_{1}\cap P_{2}=\emptyset$. In this case,
we could construct a rdf $f$ with $f^{-1}(0)\coloneqq V\setminus(P_{1}\cup
P_{2})$, $f^{-1}(1)\coloneqq P_{1}$ and $f^{-1}(0)\coloneqq P_{2}$. So if
there would exist a rhs $(R_{1},R_{2})$ with $|R_{1}|+2\cdot|R_{2}|\leq k$ and
$R_{1}\cap R_{2}\neq\emptyset$, then $(R_{1}\setminus R_{2},R_{2})$ is also a
rhs, as each $v\in R_{1}\cap R_{2}$ is dominated by itself.

Slightly abusing notions, we will call Roman Hitting Function and Roman
Hitting Set _optimization problems_ , as there is an underlying minimization
problem in each case, which is not the case for the other problems, summarized
as _extension problems_. When viewed as parameterized problems, their
_standard parameter_ is the upper bound $k$ given on the weight of the rhf or
rhs that we are looking for. Similarly, we address Extension Roman Hitting
Function and Extension Roman Hitting Set as _extension problems_. Their
_standard parameter_ is the weight of the given function $f:X\to\\{0,1,2\\}$
or of the given tuple $(U_{1},U_{2})\leq(I,X)$.

###  2.5 Organization of the Paper and Main Results

In section 3, we will prove that our optimization problems are NP-complete
and, more interestingly, if viewed as standard-parameterized problems, they
become $\textsf{W}[2]$-complete. Then, we turn our attention to the extension
problems for both variations. Recall that the algorithmic results in the case
of Roman domination were based on some basic combinatorial insights that we
actually repeat at the end of this section for the reader’s convenience.
Following this logic, first we show in section 4 a combinatorial
characterization of minimal rhs that we can make use of in section 5 where we
prove that Extension Roman Hitting Set can be solved in polynomial time. After
having derived a collection of interesting combinatorial properties of minimal
rdf in section 6, we can exhibit a corresponding result for Extension Roman
Hitting Function with surjective correspondences in section 7. In section 8,
we return to Roman domination and consider a variant of the extension problem
where we give both lower and upper bound conditions to the minimal Roman
dominating function that we are looking for. In contrast to the original
problem (that only provides an lower bound), this two-sided extension problem
turns out to be NP-complete, as we show. Also a natural parameterization of
this problem by the weight of the lower bound function (motivated by the
principle of distance to triviality [GuoHufNie2004]) does not really help, it
rather yields a parameterized problem that is complete in the class
$\textsf{W}[3]$, as we prove. These results are then employed in section 9 to
prove that in general, the extension problem for rhf is complete in the class
$\textsf{W}[3]$ when parameterized by the weight of the given function. This
inspires our studies of section 10, where we investigate alternative
parameterizations for this extension problem, sometimes proving hardness
results, but sometimes also arriving at FPT-results. In section 11, we show
how our results from section 4 and from section 5 can be used to develop an
algorithm that enumerates all minimal rhs with polynomial space and with
polynomial delay. We also analyze this algorithm from the perspective of
input-sensitive enumeration and show that its running time cannot be
substantially improved in general by providing a rather simple lower-bound
example. In section 12, we explain a quite simple branching algorithm for
computing minimum rhs. Motivated by our insights on rhs, we show in subsection
13.2 how problems like Roman Vertex Cover and Roman Edge Cover can be defined
and how our previous results also imply algorithmic results for these
problems. In particular, we show an (optimal) FPT-enumeration algorithm for
minimal Roman vertex covers. We conclude with a discussion of our results and
further lines of research. Let us mention already here that with our approach,
feasibility in the sense of enumerability of minimal solutions with polynomial
delay goes hand-in-hand with feasibility in the sense of polynomial-time
solvability of the corresponding extension problem. This need not be the case,
even in the area of domination-type problems. As shown in [CasFKMS2019a], the
extension problem for edge dominating sets is NP-complete, while minimal edge
dominating sets can be listed with polynomial delay, as shown in
[KanLMNU2015].

##  3 Optimization Problems

This section will discuss the (parameterized) complexity of the optimization
problems. The probably most natural parameterization for both problems is the
upper bound $k$ on the weight of the rhf or rhs. For our results, we will use
the $\textsf{W}[2]$-completeness of Roman Domination (with standard
parameterization) shown in [Fer08].

######  Theorem 3.1.

RHF and RHS are NP-complete. From the parameterized perspective, standard-RHF
and standard-RHS are $\textsf{W}[2]$-complete.

######  Proof 3.2.

As discussed in section 2, rdf can be interpreted as rhf and hence as rhs, so
that all hardness claims translate from Roman Domination.

We only prove the membership of (standard-)Roman Hitting Function within
$\textsf{W}[2]$. The reduction for (standard-)Roman Hitting Set is easier.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph, $\tau:X\rightarrow I$ be
a correspondence (hence, $x\in\tau(x)$ for each $x\in X$) and
$k\in\mathbb{N}$. Define $G=(V,E)$ with

$\displaystyle V$ $\displaystyle=$
$\displaystyle\,\\{a,b,c\\}\cup\overbrace{\\{v_{x}\mid x\in
X\\}}^{=:V(X)}\cup\,W\cup U,\quad\text{where}$ $\displaystyle W$
$\displaystyle=$ $\displaystyle\\{w_{i}\mid i\in I\\}\quad\text{and}$
$\displaystyle U$ $\displaystyle=$ $\displaystyle\\{u_{i}\mid i\in
I,\tau^{-1}(i)=\emptyset\\},$ $\displaystyle E$ $\displaystyle=$
$\displaystyle\\{\,\\{a,b\\},\\{a,c\\}\,\\}\cup\\{\,\\{a,v_{x}\\}\mid x\in
X\\}\cup\\{\,\\{v_{x},w_{i}\\}\mid i\in I,x\in s_{i}\\}$ $\displaystyle\cup$
$\displaystyle\\{\,\\{v_{x},u_{i}\\}\mid i\in I,x\in s_{i},u_{i}\in
U\\}\cup\\{\,\\{v_{x},v_{y}\\}\mid x,y\in X\\}.$

######  Claim 1.

$H=(X,\hat{S})$ with $\tau$ has a rhf of weight at most $k$ if and only if $G$
has a rdf with weight at most $k+2$.

######  Proof 3.3 (Proof of the claim).

Let $f\in\\{0,1,2\\}^{X}$ be minimal rhf on $H$ with $\tau$. Define
$g:V\rightarrow\\{0,1,2\\}$,

$v\mapsto\begin{cases}2,&v\in\\{a\\}\cup\\{v_{x}\mid x\in X:\>f(x)=2\\}\\\
1,&v\in\\{w_{i}\in W\mid\exists x\in\tau^{-1}(i):\>f(x)=1\\}\\\
0,&v\in\\{b,c\\}\cup\\{w_{i}\in W\mid\forall x\in\tau^{-1}(i):\>f(x)\neq
1\\}\cup U\end{cases}.$

As $g(a)=2$, $N[a]=\\{a,b,c\\}\cup V(X)$ is dominated. Let $u_{i}\in U$ for
some $i\in I$. Since $\tau^{-1}(i)=\emptyset$ and as $f$ is a rhf, there
exists an $x\in X\cap s_{i}$ with $f(x)=2$. This implies the existence of
$v_{x}\in V(X)\cap N(u_{i})$ with $g(v_{x})=2$. Therefore, each vertex in $U$
is dominated. Let $w_{i}\in W$ for some $i\in I$ with $g(w_{i})=0$. Thus,
$f(x)\neq 1$ for each $x\in\tau^{-1}(i)$. As $f$ is a rhf, there exists an
$x\in X\cap s_{i}$ with $f(x)=2$. Hence, $w_{s_{i}}$ is dominated by some
$v_{x}$ and $g$ is a rdf.

$\begin{split}\sum_{v\in V}g(v)&=2+\sum_{x\in X\text{ with
}f(x)=2}g(v_{x})+\sum_{i\in I,(\exists x\in\tau^{-1}(i):\>f(x)=1)}g(w_{i})\\\
&\leq 2+\sum_{x\in f^{-1}(2)}f(x)+\sum_{x\in f^{-1}(1)}f(x)\leq
k+2\,.\end{split}$

For the other direction, assume $f\in\\{0,1,2\\}^{V}$ is a rdf on $G$. Without
loss of generality, if there exist $v,w\in V$ with $N[w]\subseteq N[v]$ and
$f(v)+f(w)\geq 2$, then $f(v)=2$ and $f(w)=0$. We can assume this, since each
other variation would dominate at most the same vertices. Consequently, we
have $\\{v\in V\mid f(v)=2\\}\subseteq\\{a\\}\cup\\{v_{x}\mid x\in X\\}$.

Let $u,v,w\in V$ with $N[u]\cup N[w]\subseteq N[v]$ and $f(u)+f(v)+f(w)\geq
2$. Assume $f(u)=f(w)=1$. Define $h\in\\{0,1,2\\}^{V}$ with

$v\mapsto\begin{cases}f(x),&x\notin\\{u,v,w\\}\\\ 0,&x\in\\{u,w\\}\\\
2,&x=v\end{cases}.$

$N[u]\cup N[w]$ is dominated (with respect to $h$) by $v$. The other vertices
are dominated as with $f$ and $\sum_{v\in V}h(v)\leq\sum_{v\in V}f(v)$. Thus,
w.l.o.g., $f(a)=2$ and $f(x)=0$ for $x\in\\{b,c\\}\cup\\{w_{i},u_{i}\mid i\in
I:\>\tau^{-1}(i)=\emptyset\\}$. Furthermore, $W\cap f^{-1}(2)$ is empty, since
we could swap the value of a vertex under $f$ in this set with any of his
neighbors. For each $w_{i}\in W$ with $f(w_{i})=1$, there has to exist an
$x_{i}\in\tau^{-1}(i)$.

Define $g\in\\{0,1,2\\}^{X}$ with $g(x)=2$ for if $f(v_{x})=2$, $g(x_{i})=1$
defined for $x_{i}\in\tau^{-1}(i)$ as above, i.e., there is some $w_{i}\in W$
with $f(w_{i})=1$, and $f(x)=0$, otherwise. Consider $i\in I$ with no $x\in X$
such that $g(x)=1$ and $\tau(x)=i$ hold. Thus, $f(w_{i})=0$ and there exists a
$v_{x}\in V(X)\cap N(w_{i})$ with $f(v_{x})=2$. Hence, there exists an $x\in
s_{i}$ with $f(x)=2$. Therefore, $g$ is a rhf. Furthermore,

$\sum_{x\in X}g(x)=\sum_{x\in X:\>f(v_{x})=2}g(x)+\sum_{x_{s_{i}}\in
X:\>f(w_{i})=1}g(x_{i})=\sum_{v\in V}f(v)-2\leq k.$

$\Diamond$

This concludes the description of the working of our polynomial-time reduction
and serves to prove both membership in NP and membership in $\textsf{W}[2]$.

To prove $\textsf{W}[2]$-membership for standard-Roman Hitting Set, we do not
need the vertices in $\\{u_{i}\mid i\in I:\>\tau^{-1}(i)=\emptyset\\}$.
Furthermore, the argument is easier because the elements of $S$ could be part
of the solution. We omit further details here.

######  Remark 3.4.

Roman Hitting Function and Roman Hitting Set can be reduced at each other
easily.

From Roman Hitting Function to Roman Hitting Set. Let $H=(X,(s_{i})_{i\in I})$
a hypergraph with correspondence $\tau$ and $k\in\mathbb{N}$. Define
$H^{\prime}=(X,(s_{i})_{i\in I\cup I^{\prime}})$ with
$I^{\prime}=\\{i^{\prime}\mid i\in I,\tau^{-1}(i)=\emptyset\\}$ and
$s_{i^{\prime}}=s_{i}$ for each $i^{\prime}\in I^{\prime}$. We will now show
that there is a rhf on $H$ with $\tau$ of weight $k$ if and only if there is a
minimal rhs on $H^{\prime}$ of weight $k$. If there is a rhf $f$ on $H$ of
weight at most $k$, then $\left(\tau\left(f^{-1}(1)\right),f^{-1}(2)\right)$
is a rhs on $H^{\prime}$ with weight at most $k$. Let $(R_{1},R_{2})$ be a rhs
on $H^{\prime}$ of weight $k$. If there is a $i^{\prime}\in I^{\prime}\cap
R_{1}$, then $s_{i}\cap R_{2}$ is not empty or $i\in R_{1}$. In the first case
$(R_{1}\setminus\\{i^{\prime}\\},R_{2})$ would also be a rhs. Otherwise, let
$x\in s_{i}$ be an arbitrary element, then
$(R_{1}\setminus\\{i,i^{\prime}\\},R_{2}\cup\\{x\\})$ is also a rhs with the
same weight. Therefore, we can assume $I^{\prime}\cap R_{1}=\emptyset$.
Analogously, $\\{i\in I\mid\tau^{-1}(i)=\emptyset\\}\cap R_{1}=\emptyset$
holds. For each $i\in R_{1}$, $x_{i}\in\tau^{-1}(i)$ be an arbitrary element.
Then $f\in\\{0,1,2\\}^{X}$ with $f^{-1}(1)=\\{x_{i}\mid i\in R_{1}\\}$ and
$f^{-1}(2)=R_{2}$ is a rhf with weight at most $k$.

From Roman Hitting Set to Roman Hitting Function. Let $H=(X,(s_{i})_{i\in I})$
be a hypergraph and $k\in\mathbb{N}$ with $k<|I|$, as for $|I|\leq k$, we have
a trivial yes-instance. Therefore, $(I,\emptyset)$ is not a solution for the
Roman Hitting Set instance. Define the hypergraph $H^{\prime}\coloneqq(X\cup
I,(s^{\prime}_{i})_{i\in I^{\prime}})$ with $I^{\prime}\coloneqq I\cup\\{a\\}$
(for an $a\notin I\cup X$) and $s^{\prime}_{i}\coloneqq s_{i}\cup\\{i\\}$ for
$i\in I$ and $s^{\prime}_{a}=X$. The correspondence $\tau$ of $H$ is given by

$\tau:X\cup I\to I^{\prime},y\mapsto\begin{cases}a,&y\in X\\\ y,&y\in
I\end{cases}.$

Let $f$ be a rhf on $H^{\prime}$ with $\omega\left(f\right)\leq k$. As each
$i\in I$ is only in one edge, we can assume $f(i)\neq 2$ (otherwise,
$f-\chi_{\\{i\\}}$ is also a rhf with smaller weight). Hence, to hit each edge
of $(s^{\prime}_{i})_{i\in I}$ with weight at most $k<|I|$, $f^{-1}(2)\cap X$
is not empty. Thus, $s^{\prime}_{a}$ hit. If there would be an $x\in
f^{-1}(1)\cap X$, then $f-\chi_{\\{x\\}}$ is also a rhf with smaller weight.
Therefore, we have $f^{-1}(1)\subseteq I$ and $f^{-1}(2)\subseteq X$.
Furthermore, $(f^{-1}(1),f^{-1}(2))$ is a rhs with weight at most $k$. Now let
$(R_{1},R_{2})$ be a rhs on $H$ with weight $k$, then $f\in\\{0,1,2\\}^{X\cup
I}$ with $f^{-1}(1)=R_{1}$ and $f^{-1}(2)=R_{2}$ is a rhf with
$\omega\left(f\right)=k$.

The fact that Roman Domination is NP-complete even on split graphs was
mentioned repeatedly in the literature, for instance, in [Cocetal2004,
Lieetal2008], but to the best of our knowledge, no proof of this fact has been
published. We will provide a strengthened assertion in the following. Recall
that two vertices $u,v$ in a graph are called _true twins_ if $N[u]=N[v]$.

######  Lemma 3.5.

RD is NP-complete even on true-twin-free split graphs. Likewise, standard-
Roman Domination is $\textsf{W}[2]$-complete on true-twin-free split graphs.

######  Proof 3.6.

The construction provided in Theorem 3.1 shows how to construct a graph $G$ as
an instance of Roman Domination, given an instance of Roman Hitting Function.
It is not hard to observe that this graph $G$ is indeed a split graph, as (in
the notation of the proof of Theorem 3.1) $V(X)\cup\\{a\\}$ is a clique, while
$\\{b,c\\}\cup W\cup U$ is an independent set. Hence, any true twins must
belong to $V(X)\cup\\{a\\}$. As argued in the proof of Theorem 3.1, $g(a)=2$
is enforced by $b,c\in N(a)$ (ensures $g(v_{x})\neq 1$, as Theorem 2.4 would
imply the existence of a smaller rhf). As $b,c\notin N(V(X))$, there is no
$x\in V(X)$ with $N[x]=N[a]$, i.e., true twins must be in $V(X)$. We now walk
through $V(X)$ in an arbitrary but fixed order, possibly deleting vertices
from the graph that are bigger than the currently considered one, and possibly
also adding some further vertices to the independent set. Let $T(x)=\\{y\in
V(X)\mid N[y]=N[x]\\}$ be the set of twins of $x$. If $|T(x)|>1$, we delete
$T(x)\setminus\\{x\\}$ from the graph.The resulting graph gives an instance
that is a twin-free split graph that has a Roman dominating function of weight
at most $k$ if and only if the original hypergraph has.

The hardness part of the proof of Theorem 3.1 (implicitly) uses the fact that
the sequence of hyperedges could include a hyperedge multiple times, as there
could be twins (vertices with the same closed neighborhoods) in the original
graph. Consider a complete graph $K_{n}=([n],E_{n})$ with $n\geq 2$ vertices.
Since the closed neighborhoods are always equal to $[n]$, if we would use a
normal set for the hyperedges instead of a sequence of hyperedges, then the
best solution would be $\chi_{\\{v\\}}$ for any vertex $v$. This would even
not be a rdf. Namely, minimal rdf would be of the form $2\cdot\chi_{\\{v\\}}$
for any vertex $v$, or they would be constant $1$. Nevertheless, the following
holds, revisiting 3.5.

######  Corollary 3.7.

Roman Hitting Function and Roman Hitting Set are NP-complete even on simple
hypergraphs. Furthermore, standard-Roman Hitting Function and standard-Roman
Hitting Set are $\textsf{W}[2]$-complete.

Let us think about Roman Hitting Function and Roman Hitting Set as
minimization problems for some moments. We mentioned already that Minimum RD
can be approximated up to a logarithmic factor. The idea of the proof of
[Pagetal2002] can be easily adapted to Roman Hitting Function and Roman
Hitting Set and gives us the next result, which we also combine with
supplementing hardness results.

######  Theorem 3.8.

There is a polynomial-time algorithm that, given an instance
$H=(X,(s_{i})_{i\in I})$ of Minimum RHS, outputs a rhs $(R_{1},R_{2})\in
2^{I}\times 2^{X}$ such that $\omega(R_{1},R_{2})\leq
2\cdot(\ln(|I|)+1)\cdot\text{opt}(H)$. Moreover, unless
$\textsf{P}=\textsf{NP}$, there is no polynomial-time algorithm that achieves
an approximation ratio better than
$\frac{1}{2}(\ln(|I|)-o(1))\cdot\text{opt}(H)$.

######  Proof 3.9.

The claimed algorithm would run the well-known greedy algorithm for Hitting
Set (or Set Cover in the dual interpretation; see [Chv79]) on the underlying
simple hypergraph and will get a collection $C\subseteq X$ that covers
$S=\left\\{s_{i}\mid i\in I\right\\}$. Compared to the optimum cover $C^{*}$,
Chvátal [Chv79] proved that $|C|\leq(\ln(|S|)+1)\cdot|C^{*}|$. Clearly,
$(\emptyset,C)$ is a valid rhs with $\omega(\emptyset,C)=2|C|$. Conversely,
let $R^{*}=(R_{1}^{*},R_{2}^{*})$ be an optimum rhs solution, i.e.,
$\omega(R^{*})=\text{opt}(H)$. We can obtain a valid solution to the
interpretation of $H$ as a Hitting Set instance by defining
$C_{R^{*}}=\phi(R_{1}^{*})\cup R_{2}^{*}$, where $\phi$ applied to an index
set like $R_{1}^{*}$ will pick, for each index $i\in R_{1}^{*}$, an arbitrary
element from $s_{i}\subseteq X$. Clearly,
$|C^{*}|\leq|C_{R^{*}}|\leq\omega(R^{*})\leq 2\cdot|C_{R^{*}}|$. Putting the
derived inequalities together and finally observing $|S|\leq|I|$ gives the
claim on the approximation factor of the described greedy algorithm:

$\omega(R)=2|C|\leq 2\cdot(\ln(|S|)+1)\cdot|C^{*}|\leq
2\cdot(\ln(|I|)+1)\cdot\omega(R^{*})\,.$

Now, consider some polynomial-time approximation algorithm $A$ for Minimum RHS
that achieves an approximation ratio of $r(|I|)$, given an instance with index
set $I$. Let $H=(X,S)$ be a simple hypergraph, as an instance of Minimum
Hitting Set with an optimum hitting set $C^{*}\subseteq X$. We interpret this
as an instance of Minimum RHS and run $A$ on it, getting some solution
$R=(R_{1},R_{2})$. Compared to an optimum solution $R^{*}$ for this Minimum
RHS instance, we know that $\omega(R)\leq r(|S|)\cdot\omega(R^{*})$. Let
$C_{R}=\phi(R_{1})\cup R_{2}$, similar as above. Again,
$|C_{R}|\leq\omega(R)\leq 2\cdot|C_{R}|$. If $C_{R}$ achieves an approximation
ratio better than $(\ln(|S|)-o(1))\cdot|C^{*}|$, then $\textsf{P}=\textsf{NP}$
by the famous results of Dinur and Steuer [DinSte2014]. But this would be the
case if $r(|S|)\leq\frac{1}{2}(\ln(|S|)-o(1))$, because then we find:

$|C_{R}|\leq r(|S|)\cdot\omega(R^{*})\leq
r(|S|)\cdot\omega((\emptyset,C^{*}))\leq r(|S|)\cdot
2|C^{*}|\leq(\ln(|S|)-o(1))\cdot|C^{*}|\,,$

because we could interpret again the Minimum Hitting Set solution $C^{*}$ as a
solution $(\emptyset,C^{*})$ of weight $2|C^{*}|$ that is clearly not better
than an optimum Minimum RHS solution $R^{*}$.

There is clearly a small gap between lower and upper bound in the previous
theorem, but there is also a gap in the corresponding (in)approximability
result concerning Minimum Roman Domination in [Pagetal2002] that is simply not
made explicit. However, our reasoning, together with the reductions given at
the beginning of this section, prove that also in that case, we still have a
multiplicative gap of four. We can get a similar result for Minimum RHF.

######  Corollary 3.10.

There is a polynomial-time algorithm that, given an instance
$H=(X,(s_{i})_{i\in I})$ of Minimum RHF, outputs a rhf $f\in\\{0,1,2\\}^{X}$
such that $\omega(f)\leq 2\cdot(\ln(|I|)+1)\cdot\text{opt}(H)$. Moreover,
unless $\textsf{P}=\textsf{NP}$, there is no polynomial-time algorithm that
achieves an approximation ratio better than
$\frac{1}{2}(\ln(|I|)-o(1))\cdot\text{opt}(H)$.

The proof works the same as the proof for Theorem 3.8, but the result of our
algorithm is $f\in\\{0,1,2\\}^{X}$ with $f^{-1}(1)=\emptyset$ and
$f^{-1}(2)=C$. Furthermore, for a rhf $g$ we define the hitting set
$C_{g}\coloneqq f^{-1}(1)\cup f^{-1}(2)$.

Together with the construction given in 3.5, we can deduce the same
inapproximability result for Minimum RD on true-twin-free split graphs, hence
sharpening previously published results of this type.

The NP-completeness of both optimization problems also motivates our analysis
of the extension problems; it could also help speed up an exact branching
algorithm for solving these decision problems.

##  4 Combinatorial Properties of Minimal Roman Hitting Sets

In order to pave the ground for our algorithmic results, we are now going to
derive a combinatorial characterization of minimal rhs, tightly linking them
to the notion of inclusion-wise minimal hitting sets.

######  Lemma 4.1.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ a hypergraph and $(R_{1},R_{2})$ a
minimal rhs. Then for each $i\in I$, $s_{i}\cap R_{2}=\emptyset$.

######  Proof 4.2.

Assume there is a minimal rhs $R=(R_{1},R_{2})$ of $H$ with an $i\in I$ such
that $s_{i}\cap R_{2}\neq\emptyset$. Then
$R^{\prime}\coloneqq(R_{1}\setminus\\{i\\},R_{2})\leq(R_{1},R_{2})$. Since
$s_{i}\cap R_{2}$ is not empty, $i$ is hit by $R^{\prime}$. For $j\in
I\setminus\\{i\\}$, $s_{j}$ is hit by $R^{\prime}$ in the same way as by $R$.
Therefore, $R$ is not minimal.

######  Lemma 4.3.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ a hypergraph and $(R_{1},R_{2})$ a
minimal rhs. Then $R_{2}$ is a minimal hitting set on
$H^{\prime}=(X,(s_{i})_{i\in I\setminus R_{1}})$.

######  Proof 4.4.

Assume there is a minimal rhs $R=(R_{1},R_{2})$ of $H$ such that $R_{2}$ is no
minimal hitting set. $R_{2}$ has to be hitting set, as otherwise $R$ would not
be a rhs. This implies there exists a $x\in R_{2}$ such that for each
$i\in\mathbf{I}(x)$ there exists a $y_{i}\in
s_{i}\cap(R_{2}\setminus\\{x\\})$. Define
$R^{\prime}\coloneqq(R_{1},R_{2}\setminus\\{x\\})$. The indices in
$I\setminus\mathbf{I}(x)$ are hit by $R^{\prime}$ in the same way as by $R$.
As for each $i\in\mathbf{I}(x)$, $s_{i}\cap(R_{2}\setminus\\{x\\})$ is not
empty, $\mathbf{I}(x)$ is hit by $R^{\prime}$. Therefore, $R^{\prime}$ is a
rhs and $R$ not minimal.

######  Theorem 4.5.

Let $X$ be a vertex set, $\hat{S}=\left(s_{i}\right)_{i\in I}$ be a hyperedge
sequence. Then, a tuple $(R_{1},R_{2})\leq(I,X)$ is a minimal rhs if and only
if the following constraints hold:

  1. 1.

$\forall i\in R_{1}:\>s_{i}\cap R_{2}=\emptyset$,

  2. 2.

$R_{2}$ is a minimal hitting set on $\\{s_{i}\in S\mid i\in I\setminus
R_{1}\\}$.

######  Proof 4.6.

The “only if”-part of this proof follows by 4.1 and 4.3. For the other part,
we assume that the tuple $R=(R_{1},R_{2})$ fulfills the two constraints. Since
$R_{2}$ is a minimal hitting set on $\\{s_{i}\in S\mid i\in I\setminus
R_{1}\\}$, for each $i\in I$, $i$ in $R_{1}$ or $s_{i}\cap R_{2}$ is not
empty. Therefore, $R$ is a rhs. Now assume there is a minimal rhs
$R^{\prime}=(R^{\prime}_{1},R^{\prime}_{2})$ with $R^{\prime}\leq R$. Let
$x\in R_{2}\setminus R_{2}^{\prime}$. Then for each $i\in\mathbf{I}(x)$ either
$i\in R^{\prime}_{1}\subseteq R_{1}$ (this contradicts the first constraint)
or $s_{i}\cap(R^{\prime}_{2})\subseteq s_{i}\cap(R_{2}\setminus\\{x\\})$ is
not empty (this contradicts the second constraint). This implies
$R_{2}=R^{\prime}_{2}$. Let $i\in R_{1}\setminus R^{\prime}_{1}$. Then there
has to be a $x\in s_{i}\cap R^{\prime}_{2}=s_{i}\cap R_{2}$. This is a
contradiction to Constraint 1. Therefore, $R^{\prime}=R$.

######  Remark 4.7.

Now we will compare this characterization theorem with Theorem 2.5. Therefore,
let $G=(V,E)$ be a graph and $G_{nb}=(V,(N[v])_{v\in V})$ be the corresponding
closed-neighborhood hypergraph. We want to show that for a function
$f:V\rightarrow\\{0,1,2\\}$ the constraints from Theorem 2.5 with respect to
$G$ are the same as the constraints of Theorem 4.5 for the tuple
$R_{f}=(f^{-1}(1),f^{-1}(2))$ with respect to $G_{nb}$.

First, we show that the first constraint of Theorem 2.5 implies the first
constraint of Theorem 4.5 by contraposition. If there would exist $v\in
f^{-1}(1)$ and $w\in N[v]\cap f^{-1}(2)$, then $N[f^{-1}(2)]\cap f^{-1}(1)$
would not be empty. Conversely, the existence of an element $v\in
N[f^{-1}(2)]\cap f^{-1}(1)$ would imply that there is a $w\in f^{-1}(2)\cap
N[v]$. This would contradict Constraint 1 in Theorem 4.5. Thus, this
constraint is equivalent to the Constraint 1 of Theorem 2.5 in this setting.

The equivalence of the other two constraints follows by the fact that the
closed-neighborhood hypergraph $G_{nb}^{\prime}$ of $G^{\prime}=G[V\setminus
f^{-1}(1)]$ from Theorem 2.5 can be expressed as $(V\setminus
f^{-1}(1),\linebreak[3](N[v]\setminus f^{-1}(1))_{v\in V\setminus
f^{-1}(1)})$. In subsection 2.3, we mentioned that a set is a dominating set
in a graph if and only if it is a hitting set on its closed-neighborhood
hypergraph. Clearly, also the minimality adapts.

##  5 Extension Roman Hitting Set and PO-Extension Roman domination

In this section, we will consider the complexity of Extension Roman Hitting
Set. We do this by using the fact that PO-Extension Roman Domination is
polynomial-time solvable (see [AbuFerMan2022]). Furthermore, we introduce an
explicit polynomial-time algorithm.

######  Theorem 5.1.

Extension Roman Hitting Set is polynomial-time solvable.

######  Proof 5.2.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a (not necessarily simple) hypergraph
and $U=(U_{1},U_{2})\leq(I,X)$ with $X=\\{x_{1},\ldots,x_{n}\\}$, i.e.,
$I=[m]$. Define $G=(V,E)$ and $f\in\\{0,1,2\\}^{V}$ with

$\begin{split}V\coloneqq{}&\\{a,b\\}\cup\\{v_{1},\ldots,v_{n}\\}\cup\\{w_{i}\mid
i\in I\\}\\\
E\coloneqq{}&\binom{\\{a,v_{1},\ldots,v_{n}\\}}{2}\cup\\{\\{v_{j},w_{i}\\}\mid
x_{j}\in s_{i}\\}\cup\\{\\{a,b\\}\\}\\\ &\text{and, for each $v\in V$,}\\\
f(v)\coloneqq{}&\begin{cases}0,&v\in\\{b\\}\cup\\{w_{i}\mid i\notin
U_{1}\\}\cup\\{v_{j}\mid x_{j}\notin U_{2}\\}\\\ 1,&v\in\\{w_{i}\mid i\in
U_{1}\\}\\\ 2,&v\in\\{a\\}\cup\\{v_{j}\mid x_{j}\in
U_{2}\\}\end{cases}.\end{split}$

Notice that $G$ is a split graph, where the clique basically consists of the
original hypergraph vertices, with $v_{j}$ modeling $x_{j}$, plus $a$, and the
independent set is formed by vertices $w_{i}$ representing the hyperedges
$s_{i}$, plus $b$, and adjacency between $w_{i}$ and $v_{j}$ models incidence
of $s_{i}$ with $x_{j}$.

Assume there exists a PO-minimal rdf $g$ on $G$ with $f\leq g$. Define
$R=(R_{1},R_{2})$ with $R_{1}\coloneqq\\{i\mid f(w_{i})\neq 0\\}$ and
$R_{2}\coloneqq\\{x_{i}\mid f(v_{i})=2\\}$. Let $i\notin R_{1}$. Then there
exists a $v_{j}\in N(w_{i})\cap g^{-1}(2)$. This implies the existence of an
$x_{j}\in R_{2}\cap s_{i}$. Hence, $R$ is a rhs. Assume there is an $i\in
R_{1}$ such that $(R_{1}\setminus\\{i\\},R_{2})$ is also a rhs. Thus, there
exists an $x_{j}\in s_{i}\cap R_{2}$. This would contradict the PO-minimality
of $g$, as $w_{i}\in f^{-1}(\\{1,2\\})$, $f(v_{j})=2$ and $N[w_{i}]\subseteq
N[v_{j}]$ (i.e., $g-\chi_{\\{w_{i}\\}}$ is also a rdf). Assume there is a
$x_{j}\in R_{2}$ such that $(R_{1},R_{2}\setminus\\{x_{j}\\})$ is also a rhs.
Therefore, each $i\in I$ with $x_{j}\in s_{i}$ is either in $R_{1}$ or there
is another $x_{t_{i}}\in R_{2}\cap(s_{i}\setminus\\{x_{j}\\})$. Thus, vertex
$v_{j}$ has no private neighbor, which means that $g$ is not PO-minimal.
Hence, $(R_{1},R_{2})$ is a minimal rhs with
$(U_{1},U_{2})\leq({R_{1}},R_{2})$.

Conversely, let $(R_{1},R_{2})$ be a minimal rhs with
$(U_{1},U_{2})\leq({R_{1}},R_{2})$. Define

$g:\>V\rightarrow\\{0,1,2\\},\,v\mapsto\begin{cases}0,&v\in\\{b\\}\cup\\{w_{i}\mid
i\notin R_{1}\\}\cup\\{v_{j}\mid x_{j}\notin R_{2}\\}\\\ 1,&v\in\\{w_{i}\mid
i\in R_{1}\\}\\\ 2,&v\in\\{a\\}\cup\\{v_{j}\mid x_{j}\in R_{2}\\}\end{cases}.$

As $g(a)=2$, the vertices $a,b,v_{1}\ldots,v_{n}$ are dominated. Since
$(R_{1},R_{2})$ is a rhs, for each $w_{i}\in g^{-1}(0)$ there is a $v_{j}\in
N(w_{i})\cap g^{-1}(2)$. Thus, $g$ is a rdf. Assume there exists a $w_{i}\in
g^{-1}(1)$ which has a neighbor in $v_{j}\in g^{-1}(2)$. This implies there
exists an $i\in R_{1}$ with $x_{j}\in s_{i}\cap R_{2}$. But then
$(R_{1}\setminus\\{i\\},R_{2})$ is also a rhs. This leaves us to show that
each $v\in g^{-1}(2)$ has a private neighbor. By construction, $b$ is a
private neighbor of $a$. Assume there exists a $v_{j}\in V$ such that each
$u\in N[v_{j}]$ has a neighbor $t\in(N[u]\cap g^{-1}(2))\setminus\\{v_{j}\\}$.
Therefore, each $s_{i}\in\mathbf{S}(x_{j})$ has an $x_{z}\in(R_{2}\cap
s_{i})\setminus\\{x_{j}\\}$. This contradicts Theorem 4.5. Therefore, $g$ is
PO-minimal.

Let $G=(V,E)$ be a graph and $f:V\rightarrow\\{0,1,2\\}$ be a mapping. Theorem
6 of [AbuFerMan2022] implies that, if we solve the Ext-RHS on
$H=(V,(N[v])_{v\in V})$ with the tuple $(f^{-1}(1),f^{-1}(2))$, then we solve
the PO-Ext-RDF instance $(G,f)$. Therefore, we can view Ext-RHS as a
generalization of PO-Ext-RDF.

Algorithm 1 ExtRHS Algorithm

1:procedure ExtRHS Solver($X,\hat{S},(R_{1},R_{2})$)
Input: set $X$, $\hat{S}\coloneqq(s_{i})_{i\in I}$, $(R_{1},R_{2})\leq(I,X)$.
Output: Is there a minimal Roman hitting set $M$ with $R\leq M$?

2: for $x\in R_{2}$ do

3: for $i\in I(x)$ do

4: if $i\in R_{1}$ then

5: Return no

6: if
$\mathbf{I}\left(x\right)\subseteq\mathbf{I}\left(R_{2}\setminus\\{x\\}\right)$
then

7: Return no

8: $M_{1}\coloneqq R_{1}$

9: $M_{2}\coloneqq R_{2}$

10: for $i\in I\setminus\left(\mathbf{I}\left(M_{2}\right)\cup M_{1}\right)$
do

11: Add $i$ to $M_{1}$.

12: Return yes $(M_{1},M_{2})$

######  Theorem 5.3.

Algorithm 1 solves Ext-RHS for instances $(X,\hat{S},(R_{1},R_{2}))$ in
polynomial time.

######  Proof 5.4.

Let $H=\left(X,(s_{i})_{i\in I}\right)$ be a hypergraph and let
$(R_{1},R_{2})\leq(I,X)$ be a tuple. Assume that the algorithm returns yes.
Then $R_{1}\subseteq M_{1}$ and $R_{2}=M_{2}$, since we define $M_{1},M_{2}$
as $R_{1},R_{2}$ in the beginning and never delete any vertices from these
sets. Further, we put each index from
$I\setminus\left(\mathbf{I}\left(M_{2}\right)\cup M_{1}\right)$ into $M_{1}$.
Therefore $M=(M_{1},M_{2})$ is a rhs at the end of this algorithm. Now we want
to check if $M$ is minimal. Assume that there is an $i\in R_{1}$ such that
$s_{i}\cap M_{2}\neq\emptyset$. Since the for-loop in Line 10 does not put
such an index into $M_{1}$, $i$ has to be in $R_{1}$. Because $M_{2}=R_{2}$,
Line 5 would have returned no. Assume $R_{2}$ is not a minimal hitting set on
$(s_{i})_{i\in I\setminus M_{1}}$. Since $(M_{1},M_{2})$ is a rhs, $M_{2}$ is
a hitting set on $(s_{i})_{i\in I\setminus M_{1}}$. If $M_{2}=R_{2}$ is not
minimal, then Line 7 will return no.

Assume there is a minimal rhs $(P_{1},P_{2})$ on $H$ with
$(R_{1},R_{2})\leq(P_{1},P_{2})$, but the algorithm returns no. If the
algorithm returns no in Line 5, then there exists a $i\in R_{1}\subseteq
P_{1}$ with an $x\in s_{i}\cap R_{2}\subseteq s_{i}\cap P_{2}$. This
contradicts Theorem 4.5. Assume the algorithm returns no in Line 7. Then there
is an $x\in R_{2}\subseteq P_{2}$ such that, for each $i\in\mathbf{I}(x)$,
there exists a $y\in s_{i}\cap(R_{2}\setminus\\{x\\})$. Then $P_{2}$ can not
be a minimal hitting set on $(s_{i})_{i\in I\setminus P_{1}}$. As these are
the only cases in which the algorithm returns no, if the input is a yes-
instance, then the algorithm will return yes.

We will explain in section 11 how we can make use of this extension algorithm
for enumerating all minimal rhs with polynomial delay.

##  6 Combinatorial Properties of Minimal Roman Hitting Functions

In this section, we will prove combinatorial properties of minimal rhf. This
will help us analyze the complexity of Extension Roman hitting functions.

######  Lemma 6.1.

Let $X$ be a vertex set, $\hat{S}=\left(s_{i}\right)_{i\in I}$ be a hyperedge
sequence and $\tau:X\rightarrow I$ be a correspondence. Then for each minimal
rhf $f\in\\{0,1,2\\}^{X}$ of $X$, $\hat{S}$, $\tau$ and for all $x,y\in
f^{-1}(1)$ with $x\neq y$, $\tau(x)\neq\tau(y)$ holds, i.e.,
$\tau|_{f^{-1}(1)}$ is injective.

######  Proof 6.2.

Assume $f$ is a minimal rhf of $X$, $\hat{S}$ and $\tau$ such that there exist
$x,y\in f^{-1}(1)$ with $x\neq y$ but $\tau(x)=\tau(y)=i$. Define
$\tilde{f}=f-\chi_{\\{y\\}}$. Trivially, $\tilde{f}\leq f$ and $\tilde{f}\neq
f$. Since $f^{-1}(2)=\tilde{f}^{-1}(2)$ and
$\tau(\tilde{f}^{-1}(1))=\tau(f^{-1}(1)\setminus\\{y\\})=\tau(f^{-1}(1))$
hold, $\tilde{f}$ is a rhf. This implies that $f$ is not minimal, which is a
contradiction.

######  Lemma 6.3.

Let $X$ be a vertex set, $\hat{S}=\left(s_{i}\right)_{i\in I}$ be a hyperedge
sequence and $\tau:X\rightarrow I$ be a correspondence. Then for each minimal
rhf $f\in\\{0,1,2\\}^{X}$ of $X$, $\hat{S}$, $\tau$ and each $x\in f^{-1}(1)$,
the sets $s_{\tau(x)}$ and $f^{-1}(2)$ are disjoint.

######  Proof 6.4.

Assume $f$ is a minimal rhf of $X$, $\hat{S}$ and $\tau$ such that there
exists an $x\in f^{-1}(1)$ with $s_{\tau(x)}\cap f^{-1}(2)\neq\emptyset$.
Define $\tilde{f}=f-\chi_{\\{x\\}}$. Trivially, $\tilde{f}\leq f$ and
$f\neq\tilde{f}$. By definition of $\tilde{f}$, we have
$f^{-1}(2)=\tilde{f}^{-1}(2)$. Hence,
$s_{\tau(x)}\in\mathbf{S}(\tilde{f}^{-1}(2))$. Since $s_{i}$ ,for $i\in
I\setminus\\{\tau(x)\\}$, is hit by $\tilde{f}$ in the same way as by $f$,
$\tilde{f}$ is a rhf. This contradicts the minimality of $f$.

######  Lemma 6.5.

Let $X$ be a vertex set, $\hat{S}=\left(s_{i}\right)_{i\in I}$ be a hyperedge
sequence and $\tau:X\rightarrow I$ be a correspondence. Then for each minimal
rhf $f\in\\{0,1,2\\}^{X}$ of $X$, $\hat{S}$, $\tau$, $f^{-1}(2)$ is minimal
hitting set on $S^{\prime}\coloneqq\\{s_{i}\in S\mid i\in I,\tau^{-1}(i)\cap
f^{-1}(1)=\emptyset\\}$, i.e., each $s_{i}\in S^{\prime}$ contains a vertex
$x$ with $f(x)=2$.

######  Proof 6.6.

Assume $f^{-1}(2)$ is not a minimal hitting set on $S^{\prime}$. If there is
an $s\in S^{\prime}$ that is not hit by $f^{-1}(2)$, then $f$ is no rhf,
contradicting our assumption. Therefore, we assume that $f^{-1}(2)$ is not
minimal. Then there exists an $x\in f^{-1}(2)$ such that, for each $s\in
S^{\prime}$ with $x\in s$, there exists a
$y\in\left(f^{-1}(2)\setminus\\{x\\}\right)\cap s.$ Define
$\tilde{f}=f-2\cdot\chi_{\\{x\\}}$. Let $i\in I$. As
$\tau(f^{-1}(1))=\tau(\tilde{f}^{-1}(1))$ holds by definition, we only need to
consider $i\in I\setminus\tau(f^{-1}(1))$. For $i$ with
$s_{i}\in\mathbf{S}(f^{-1}(2))\setminus\mathbf{S}(x)$, trivially
$s_{i}\cap\tilde{f}^{-1}(2)\neq\emptyset$ . If $s_{i}\in\mathbf{S}(x)$, as we
mentioned before, there exists a
$y\in\left(f^{-1}(2)\setminus\\{x\\}\right)\cap s_{i}=\tilde{f}^{-1}(2)\cap
s_{i}$. This implies that $\tilde{f}$ is a rhf and $f$ is not minimal,
contradicting our assumption.

Altogether, these three lemmas imply the following observation:

######  Corollary 6.7.

Let $f$ be a minimal rhf. For all $x\in f^{-1}(1)$ and for all $i\in I$ that
satisfy $s_{i}=s_{\tau(x)}$, we have $f^{-1}(1)\cap\tau^{-1}(i)\neq\emptyset$.

######  Lemma 6.8.

Let $X$ be a vertex set, $\hat{S}=\left(s_{i}\right)_{i\in I}$ be a hyperedge
sequence and $\tau:X\rightarrow I$ be a correspondence. Then for each minimal
rhf $f\in\\{0,1,2\\}^{X}$ of $X$, $\hat{S}$, $\tau$, and for all $x\in
f^{-1}(2)$, there exists $i\in I\setminus\\{\tau(x)\\}$ with $s_{i}\cap
f^{-1}(2)=\\{x\\}$.

######  Proof 6.9.

Let $f$ be a minimal rhf. Assume there exists an $x\in f^{-1}(2)$ such that
for each $i\in I\setminus\\{\tau(x)\\}$, $s_{i}\cap f^{-1}(2)\neq\\{x\\}$. We
want to show that $\tilde{f}=f-\chi_{\\{x\\}}$ is also a rhf. By 6.5, there
exists an $i\in I\setminus\tau(f^{-1}(1))$ such that $s_{i}\cap
f^{-1}(2)=\\{x\\}$. The assumption on $x$ implies that $i$ has to be
$\tau(x)$. Let $j\in I$. If $x\notin s_{j}\cap f^{-1}(2)\neq\emptyset$,
$s_{j}$ is hit by $\tilde{f}$ in the same way as by $f$. The index $j=\tau(x)$
is hit by $\tilde{f}(x)=1$. For $x\in s_{j}\cap f^{-1}(2)$ with
$j\neq\tau(x)$, there has to exist another $y\in s_{i}\cap f^{-1}(2)$ besides
$x$. This leaves the indices which are hit by
$f^{-1}(1)\subseteq\tilde{f}^{-1}(1)$. Therefore, $\tilde{f}$ is a rhf.

######  Theorem 6.10.

Let $X$ be a vertex set, $\hat{S}=\left(s_{i}\right)_{i\in I}$ be a hyperedge
sequence and $\tau:X\rightarrow I$ be a correspondence. Then, a function
$f\in\\{0,1,2\\}^{X}$ is a minimal rhf if and only if the following constraint
items hold:

  1. 0.

$\forall x,y\in f^{-1}(1):\>x\neq y\Rightarrow\tau(x)\neq\tau(y)$,

  2. 1.

$\forall x\in f^{-1}(1):\>s_{\tau(x)}\cap f^{-1}(2)=\emptyset$,

  3. 2.

$\forall x\in f^{-1}(2)\,\exists i\in I\setminus\\{\tau(x)\\}:\>s_{i}\cap
f^{-1}(2)=\\{x\\}$, and

  4. 3.

$f^{-1}(2)$ is a minimal hitting set on $\\{s_{i}\in S\mid i\in
I,\tau^{-1}(i)\cap f^{-1}(1)=\emptyset\\}$.

######  Proof 6.11.

The only-if-part follows from 6.3, 6.1, 6.5 and 6.8.

Assume $f$ fulfills the constraints. By Constraint 3, we know for all $i\in
I$, either $s_{i}\cap f^{-1}(2)\neq\emptyset$, or there exists an $x\in
f^{-1}(1)$ with $\tau(x)=i$. Therefore, $f$ is a rhf. Let
$g\in\\{0,1,2\\}^{X}$ be a minimal rhf with $g\leq f$. Thus,
$g^{-1}(2)\subseteq f^{-1}(2)$ and
$\mathbf{S}(g^{-1}(2))\subseteq\mathbf{S}(f^{-1}(2))$ hold. Furthermore,
$g^{-1}(1)\subseteq f^{-1}(1)\cup f^{-1}(2)$. Since for each $x\in X$,
$\\{s_{\tau(x)}\\}\subseteq\mathbf{S}(x)$, for each $i\in\tau(g^{-1}(1))$,
$i\in\tau(f^{-1}(1))$ or $s_{i}\in\mathbf{S}(f^{-1}(2))$. Let $x\in X$ be a
element with $g(x)<f(x)$.

Case 1: $g(x)=0<2=f(x)$. This implies that, for each $i\in\mathbf{I}(x)$,
there exists a $y\in s_{i}$ with $2=g(y)\leq f(y)=2$ or $y\in\tau^{-1}(i)\cap
g^{-1}(1)\subset\tau^{-1}(i)\cap(f^{-1}(1)\cup f^{-1}(2))$. This either
contradicts Constraint 1 or Constraint 2.

Case 2: $g(x)=1<2=f(x)$. This case works analogously, somehow simpler. We only
need to exclude $i=\tau(x)$.

Case 2: $f(x)=1$. This implies $g(x)=0$. Since $g$ is a rhf, either
$s_{\tau(x)}\cap g^{-1}(2)$ is not empty or there exists a $y\in g^{-1}(1)$
with $\tau(x)=\tau(y)$.

Case 2.1: $\tau(x)\cap g^{-1}(2)\neq\emptyset$. As $g^{-1}(2)\subseteq
f^{-1}(2)$, this contradicts Constraint 1.

Case 2.2: There exists a $y\in g^{-1}(1)$ with $\tau(x)=\tau(y)$. Therefore,
either there exists a $y\in f^{-1}(1)\setminus\\{x\\}$ such that
$\tau(x)=\tau(y)$ (this contradicts Constraint  ‣ 6.10) or $y\in f^{-1}(2)$
(this contradicts Constraint 1).

Thus, $g=f$ holds. Therefore, $f$ is minimal.

######  Remark 6.12.

As in 4.7, we will compare this theorem with Theorem 2.4. Let $G=(V,E)$ be a
graph and let $G_{nb}=(V,(N[v])_{v\in V})$ be the closed-neighborhood
hypergraph. The function $\tau:V\to V$ is the identity function. Let
$f:V\to\\{0,1,2\\}$.

As $\tau$ is bijective, Constraint  ‣ 6.10 holds for each $f$. We will show
next that $f$ fulfills Constraint 1 of Theorem 6.10 if and only if $f$
fulfills Constraint 1 of Theorem 2.4. Assume there exists a $v\in f^{-1}(1)$
such that $N[v]\cap f^{-1}(2)\neq\emptyset$. This implies
$N[f^{-1}(2)]\cap\\{v\\}\subseteq N[f^{-1}(2)]\cap f^{-1}(1)$ is not empty.
This contradicts Constraint 1 of Theorem 2.4. Conversely, the existence of an
element $v\in N[f^{-1}(2)]\cap f^{-1}(1)$ would imply that there is a $w\in
f^{-1}(2)\cap N[v]$. This would contradict Constraint 1 in Theorem 6.10.

For each $v\in f^{-1}(2)$, there is a $u\in V\setminus\\{v\\}$ such that
$N[u]\cap f^{-1}(2)=\\{v\\}$ if and only if each vertex in $f^{-1}(2)$ has a
private neighbor that is not itself. We can reformulate the set occurring in
the last Constraint of Theorem 6.10 to $\\{N[v]\mid v\in V,\tau^{-1}(v)\cap
f^{-1}(1)=\emptyset\\}=\\{N[v]\mid v\in V,\,v\notin f^{-1}(1)\\}$. This is the
set of hyperedges of $(f^{-1}(\\{0,2\\}),(N[v])_{v\in V\setminus f^{-1}(1)})$.
$f^{-1}(2)$ is a minimal hitting set of this hypergraph if and only if it is a
minimal hitting set of ($(f^{-1}(\\{0,2\\}),(N[v]\setminus f^{-1}(1))_{v\in
V\setminus f^{-1}(1)})$), which is the closed-neighborhood hypergraph of
$G^{\prime}=G[f^{-1}(\\{0,2\\})]$. Therefore, the last Constraints of Theorem
2.4 and Theorem 6.10 are equivalent in this case.

We call a $f\in\\{0,1,2\\}^{X}$ _extensible_ on the hypergraph $H=(X,\hat{S})$
with correspondence $\tau$ if there exists a minimal rhf $g$ with $f\leq g$.

######  Corollary 6.13.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph with correspondence
$\tau$ and $f\in\\{0,1,2\\}^{X}$ be a function with $x\in f^{-1}(2)$, $y\in
f^{-1}(1)$ and $x\in s_{\tau(y)}$. Then, $f$ is extensible if and only if
$f+\chi_{\\{y\\}}$ is extensible.

######  Proof 6.14.

Since $\leq$ on $\mathbb{N}^{X}$ is transitive, if $f+\chi_{\\{y\\}}$ is
extensible, then so is $f$. For the other direction, we assume that there
exists a minimal rhf $g$ with $f\leq g$. Thus, $g(x)=f(x)=2$ and
$g(y)\in\\{1,2\\}$ for $x\in f^{-1}(2)$, $y\in f^{-1}(1)$. By Constraint 1 of
Theorem 6.10, $y\in g^{-1}(2)$, as $x\in s_{\tau(y)}$. For the remaining $z\in
X\setminus\\{y\\}$, $(f+\chi_{\\{y\\}})(z)=f(z)\leq g(z)$ holds. This implies
$f+\chi_{\\{y\\}}\leq g$, so that $f+\chi_{\\{y\\}}$ is extensible.

######  Corollary 6.15.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph with correspondence
$\tau$ and $f\in\\{0,1,2\\}^{X}$ be a function with $x,y\in f^{-1}(1)$, $x\neq
y$ and $\tau(x)=\tau(y)$. Then, $f$ is extensible if and only if
$f+\chi_{\\{x,y\\}}$ is extensible.

######  Proof 6.16.

Since $\leq$ on $\mathbb{N}^{X}$ is transitive, if $f+\chi_{\\{x,y\\}}$ is
extensible, then so is $f$. For the other direction, we assume that there
exists a minimal rhf $g$ with $f\leq g$. Thus, $g(x),g(y)\in\\{1,2\\}$. By
Constraint  ‣ 6.10 of Theorem 6.10, $g(x)=2$ or $g(y)=2$. This implies that if
$f$ is extensible, then $f+\chi_{\\{x\\}}$ or $f+\chi_{\\{y\\}}$ is
extensible. In both cases, we can use 6.13 and conclude that
$f+\chi_{\\{x,y\\}}$ is extensible if function $f$ is extensible.

######  Theorem 6.17.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph with correspondence
$\tau$, $\tau:X\rightarrow I$. Let $f\in\\{0,1,2\\}^{X}$ be a function such
that $x\neq y$ implies $\tau(x)\neq\tau(y)$ for each $x,y\in f^{-1}(1)$. Then,
$f$ is extensible if and only if there exist a set $R_{2}$ with
$f^{-1}(2)\subseteq R_{2}\subseteq f^{-1}(1)\cup f^{-1}(2)$ and a mapping
$\rho:R_{2}\to I$, satisfying the following constraints.

  1. 1.

$\forall x\in R_{2}:\>\rho(x)\neq\tau(x)$.

  2. 2.

$\forall x\in R_{2}:\>s_{\rho(x)}\cap R_{2}=\\{x\\}$.

  3. 3.

$\forall x\in f^{-1}(1)\setminus R_{2}:\>\tau(x)\cap R_{2}=\emptyset$.

  4. 4.

$\forall i\in I\text{ such that }\tau^{-1}(i)=\emptyset:\\\
s_{i}\subseteq\left(\bigcup_{x\in f^{-1}(1)\setminus
R_{2}}s_{\tau(x)}\right)\cup\left(\bigcup_{x\in
R_{2}}s_{\rho(x)}\right)\implies s_{i}\cap R_{2}\neq\emptyset$.

######  Proof 6.18.

Define $I^{\prime}\coloneqq\\{i\in I\mid\tau^{-1}(i)=\emptyset\\}$. First, we
assume that $f$ is extensible. Let $g\in\\{0,1,2\\}^{X}$ be a minimal rhf with
$f\leq g$. By 6.5, $g^{-1}(2)$ is a minimal hitting set on $\\{s_{i}\in S\mid
i\in I,\tau^{-1}(i)\cap f^{-1}(1)=\emptyset\\}$ $(*)$. With Theorem 6.10,
Constraint 2, this implies that, for each $x\in g^{-1}(2)$, there exists an
$\rho(x)\in I\setminus\\{\tau(x)\\}$ such that $s_{\rho(x)}\cap
g^{-1}(2)=\\{x\\}$. Define $R_{2}=(f^{-1}(1)\cup f^{-1}(2))\cap g^{-1}(2)$.
Clearly, $f^{-1}(2)\subseteq R_{2}\subseteq f^{-1}(1)\cup f^{-1}(2)$. We have
to check the four constraints claimed for $R_{2}$. The first two are even true
in a slightly more general fashion by $(*)$. If there would exist a $y\in
f^{-1}(1)\setminus R_{2}\subseteq g^{-1}(1)$ with $\emptyset\neq
s_{\tau(y)}\cap R_{2}\subseteq s_{\tau(y)}\cap g^{-1}(2)$, then this would
contradict Theorem 6.10, Constraint 2, showing the third constraint of this
theorem. We now turn to the fourth and last constraint. Let $i\in I^{\prime}$.
Since $\tau^{-1}(i)=\emptyset$, there has to be a $y\in g^{-1}(2)\cap s_{i}$.
If $y\in R_{2}$, then the constraint is satisfied. Hence, we can assume that
$y\in g^{-1}(2)\setminus R_{2}=g^{-1}(2)\cap f^{-1}(0)$. Consider $x\in
f^{-1}(1)\setminus R_{2}$. As $f\leq g$ and $x\notin R_{2}$, we have $g(x)=1$.
By Constraint 1 of Theorem 6.10, $y\notin s_{\tau(x)}$. If
$s_{i}\subseteq\left(\bigcup_{x\in f^{-1}(1)\setminus
R_{2}}s_{\tau(x)}\right)\cup\left(\bigcup_{x\in R_{2}}s_{\rho(x)}\right)$ and
$s_{i}\cap R_{2}=\emptyset$ hold, then this would contradict $s_{\rho(x)}\cap
R_{2}=\\{x\\}$. Therefore, all the constraints hold.

Let now $f$, $R_{2}$ and $\rho:R_{2}\to I$ fulfill the constraints of this
theorem. For this part of the proof we will define a hypergraph $H^{\prime}$
that includes each edge where $\tau(X)$ does not include its index and the
edge is not hit, yet. We will show that there is a minimal hitting set $D$ on
$H^{\prime}$ which does not include any vertex of $s_{\rho(x)}$ for $x\in
R_{2}$ or $s_{\tau(x)}$ for $f^{-1}(1)\setminus R_{2}$. $R_{2}\cup D$ will
describe the set of vertices with value 2. We will hit the remaining vertices
by assigning the value 1 to some vertices.

Therefore, we define the hypergraph
$H^{\prime}=(X^{\prime},(s^{\prime}_{i})_{i\in I^{\prime\prime}})$ with

$\displaystyle I^{\prime\prime}\coloneqq\,$ $\displaystyle
I^{\prime}\cap\\{i\in I\mid s_{i}\cap R_{2}=\emptyset\\}\,,$ $\displaystyle
X^{\prime}\coloneqq\,$ $\displaystyle\left(\bigcup_{i\in
I^{\prime\prime}}s_{i}\right)\setminus\left(\left(\bigcup_{x\in
f^{-1}(1)\setminus R_{2}}s_{\tau(x)}\right)\cup\left(\bigcup_{x\in
R_{2}}s_{\rho(x)}\right)\right)$

and $s^{\prime}_{i}\coloneqq s_{i}\cap X^{\prime}$. If $s^{\prime}_{i}$ is
empty for an $i\in I^{\prime\prime}$, then there would not exist any hitting
set on $H^{\prime}$. Therefore, we need to ensure that such an index does not
exist. Let $i\in I^{\prime\prime}$. Hence, $\tau^{-1}(i)=\emptyset$ and
$s_{i}\cap R_{2}=\emptyset$. The contraposition of the implication of
Constraint 4 implies

$s_{i}\nsubseteq\left(\bigcup_{x\in f^{-1}(1)\setminus
R_{2}}s_{\tau(x)}\right)\cup\left(\bigcup_{x\in R_{2}}s_{\rho(x)}\right).$

Hence, $s^{\prime}_{i}\neq\emptyset$ for each $i\in I^{\prime\prime}$. Thus,
there exists a minimal hitting set $D$ on $H^{\prime}$. Furthermore, the
construction of $H^{\prime}$ and $D$ implies that $\tau^{-1}(i)$ is not empty
for each $i\in I\setminus\mathbf{I}(R_{2}\cup D)$. For each $i\in
I\setminus\mathbf{I}(R_{2}\cup D)$, $x_{i}$ will describe an arbitrary vertex
in $\tau^{-1}(i)$, unless there exists an $x_{i}\in\left(f^{-1}(1)\setminus
R_{2}\right)\cap\tau^{-1}(i)$ (by assumption on $f$, there is at most one such
element). In this case, we choose this $x_{i}$.

Define $g\in\\{0,1,2\\}^{X}$ with $g^{-1}(1)=\\{x_{i}\mid i\in
I\setminus\mathbf{I}(R_{2}\cup D)\\}$ and $g^{-1}(2)=D\cup R_{2}$. We will now
use Theorem 6.10 to show that $g$ is a minimal rhf. By the construction of
$g^{-1}(1)$, the first two constraints of Theorem 6.10, i.e., Constraints  ‣
6.10 and 1, are fulfilled. Since $g^{-1}(1)$ hits each edge in
$I\setminus\mathbf{I}(D\cup R_{2})$, each hyperedge in $\\{s_{i}\mid i\in
I,\tau^{-1}(i)\cap g^{-1}(1)=\emptyset\\}$ is hit by $g^{-1}(2)$. As D is
minimal and $D\cap\left(\cup_{x\in R_{2}}s_{\rho(x)}\right)=\emptyset$,
Constraint 2 implies that is $D\cup R_{2}$ also a minimal hitting set on
$\mathbf{I}(D\cup R_{2})$. The remaining constraint of Theorem 6.10 follows by
the first two constraints of $f$ together with definition of $H^{\prime}$ and
$D$, as $H^{\prime}$ only contains hyperedges $s^{\prime}_{i}$ where
$\tau^{-1}(i)=\emptyset$.

######  Remark 6.19.

Let $H=(X,(s_{i})_{i\in I})$ be hypergraph with a correspondence $\tau$. With
a combination of 6.15 and Theorem 6.17 we can check if a function
$f\in\\{0,1,2\\}^{X}$ is extensible (and therefore if $(H,\tau,f)$ is a yes
instance of Extension Roman Hitting Function). First, we use 6.15
exhaustively, and then we can use Theorem 6.17.

######  Remark 6.20.

This Theorem already gives an idea why Extension Roman Hitting Function with
surjective correspondence (and therefore also Ext-RDF) runs in polynomial
time. Let $H=(X,(s_{i})_{i\in I})$ be a hypergraph and $f\in\\{0,1,2\\}^{X}$
be a function with the surjective correspondence $\tau$. First of all we can
disregard Constraint 4, as $\tau(i)\neq\emptyset$ for each $i\in I$. Then, we
could use the corollaries 6.13 and 6.15. We set $R_{2}\coloneqq f^{-1}(2)$. By
Constraint 3, we have to add each element in $x\in f^{-1}(1)$ with
$s_{\tau(x)}\cap R_{2}\neq\emptyset$ to $R_{2}$. This can be done in
polynomial time (we will show how in Algorithm 2). Now we can check in
polynomial time if each for each $x\in R_{2}$ there exists a $i_{x}\in I$ that
fulfills the constraints 1 and 2.

This will also be our strategy in the next section.

##  7 Ext-RHF with Surjective Correspondence and Ext-RDF

This section is presented polynomial time algorithm for Ext-RHF instances with
a surjective correspondence function $\tau$. At the end of this section, we
explain how this algorithm can be viewed as a natural generalization of Ext-
RDF that was studied before [AbuFerMan2022b].

Algorithm 2 ExtRHF Algorithm

1:procedure ExtRHF Solver($X,\hat{S},\tau,g$)
Input: set $X$, $\hat{S}\coloneqq(s_{i})_{i\in I}$, $\tau$ correspondence
function, $g\in\\{0,1,2\\}^{X}$ with $\\{i\in
I\mid\tau^{-1}(i)=\emptyset\\}\subseteq\mathbf{I}\left(g^{-1}(2)\right)$.
Output: Is there a minimal Roman hitting function $f$ with $g\leq f$?

2: $M_{2}\coloneqq g^{-1}(2)$

3: $M_{1}\coloneqq g^{-1}(1)$

4: for $x\in M_{1}$ do

5: for $y\in M_{1}\setminus\\{x\\}$ do

6: if $\tau(x)=\tau(y)$ then

7: Add $x,y$ to $M_{2}$ and delete them in $M_{1}$.

8: Continue with the next $x$.

9: $M\coloneqq M_{2}$ { All $x\in f^{-1}(2)$ are considered in the following.
}

10: while $M\neq\emptyset$ do

11: Choose $x\in M$.

12: for $y\in\tau^{-1}(\mathbf{I}\left(x\right))$ do

13: if $y\in M_{1}$ then

14: Add $y$ to $M_{2}$ and $M$. Delete $y$ in $M_{1}$.

15: Delete $x$ from $M$.

16: for $x\in M_{2}$ do

17: if
$\mathbf{I}\left(x\right)\setminus\mathbf{I}\left(M_{2}\setminus\\{x\\}\right)\subseteq\\{\tau(x)\\}$
then

18: Return no

19: for $i\in
I\setminus\left(\mathbf{I}\left(M_{2}\right)\cup\tau(M_{1})\right)$ do

20: Add one element $x\in\tau^{-1}(i)$ to $M_{1}$.

21: Return yes $\\{\,f^{-1}(0)=X\setminus\left(M_{1}\cup
M_{2}\right),f^{-1}(1)=M_{1},f^{-1}(2)=M_{2}\,\\}$

######  Theorem 7.1.

Algorithm 2 solves Ext-RHF for instances $(X,\hat{S},\tau,g)$ satisfying
$\\{i\in
I\mid\tau^{-1}(i)=\emptyset\\}\subseteq\mathbf{I}\left(g^{-1}(2)\right)$ in
polynomial time.

######  Proof 7.2.

Assume the algorithm returns yes. Define $f\in\\{0,1,2\\}^{X}$ with
$f^{-1}(0)=X\setminus\left(M_{1}\cup M_{2}\right)$, $f^{-1}(1)=M_{1}$ and
$f^{-1}(2)=M_{2}$. As we put vertices from $M_{1}$ into $M_{2}$ and from
$X\setminus(M_{1}\cup M_{2})$ into $M_{1}$ only, $g\leq f$ holds. Since
$\tau^{-1}(i)$ is not empty for each $i\in
I\setminus\mathbf{I}\left(M_{2}\right)\subseteq
I\setminus\mathbf{I}\left(g^{-1}(2)\right)$, $f$ is a rhf.
$\tau(M_{1})\cap\mathbf{I}(M_{2})$ does not contain any elements after the
while-loop. As the for-loop starting in line 19 puts elements $x\in X$ in
$M_{2}$ with $s_{\tau(x)}\cap M_{2}=\emptyset$ only,
$\tau(M_{1})\cap\mathbf{I}(M_{2})$ is empty at the end of the algorithm. The
first for-loop ensures, that two different elements in $M_{1}$ have different
values under $\tau$. Only in the last for-loop, we put an element $x$ into
$M_{1}$, which has a unique $\tau(x)$ and where $\tau(x)$ is not hit so far.
If there is a vertex $x\in M_{2}$ with
$\mathbf{I}(x)\setminus\mathbf{I}\left(M_{2}\setminus\\{x\\}\right)\subseteq\\{\tau(x)\\}$,
then the algorithm would return no. Theorem 6.10 implies that $f$ is a minimal
rhf.

Assume the algorithm return no, but there is a minimal rhf with $g\leq h$.
Therefore, the constraints of Theorem 6.10 hold for $h$. This implies that
$\mathbf{I}\left(h^{-1}(2)\right)\cap\tau(h^{-1}(1))=\emptyset$ and
$\tau(x)\neq\tau(y)$ hold for each $x,y\in h^{-1}(1)$ with $x\neq y$.
Therefore, $M_{1}\subseteq h^{-1}(1)$ and $M_{2}\subseteq h^{-1}(2)$ is
fulfilled before line 16. Therefore,
$\mathbf{I}(x)\setminus\mathbf{I}\left(h^{-1}(2)\setminus\\{x\\}\right)\subseteq\mathbf{I}(x)\setminus\mathbf{I}(M_{2}\setminus\\{x\\})=\\{\tau(x)\\}$
holds for each $x\in M_{2}$. Thus, $h$ is not a minimal rdf. Hence, Algorithm
2 solves Ext-RHF with
$I\setminus\tau(X)\subseteq\mathbf{I}\left(g^{-1}(2)\right)$.

Trivially, the for-loops run in polynomial time. As in each iteration of the
while-loop starting in Line 10 we delete a vertex in $M$ and never put this
vertex in to it again, this while-loop needs only polynomial time. Thus,
Algorithm Algorithm 2 runs in polynomial time.

This implies the following corollary.

######  Corollary 7.3.

Ext-RHF with surjective $\tau$ is polynomial-time solvable.

Let $G=(V,E)$ be a graph. Recall the closed-neighborhood hypergraph $G_{nb}$
associated to $G$, i.e., $G_{nb}=(V,(N[v])_{v\in V})$. If we compare this
algorithm on $G_{nb}$ with Algorithm 1 in [AbuFerMan2022a] on $G$, then these
algorithms would work the same. Since the correspondence $\tau$ is bijective,
$\tau(x)\neq\tau(y)$ holds for each $x,y\in X$ with $x\neq y$. Therefore, the
for-loop starting in Line 4 would not change anything. In the while loop we go
through all $x\in M_{2}$ and look for $y\in\tau^{-1}(\mathbf{I}(x))\cap
M_{1}$. The very definition of $\hat{S}$ implies that we update the value of
such a $y\in N[x]$ to $f(y)=2$. This also happens in the ExtRDF-algorithm of
[AbuFerMan2022a]. In the next step, both algorithms check if each vertex with
value 2 has private edge which is not the $\tau$-hyperedge (private neighbor
that is not the itself). In the end Algorithm 2 takes an index $i$ not hit and
sets $f(x)=1$ for one vertex $x\in\tau^{-1}(i)$. As $\tau$ is injective, the
vertex $x$ is unique. Therefore, both algorithm would work the same. Our
presented algorithm hence generalizes the polynomial-time solvability of
Extension Roman Domination.

##  8 Bounded Extension Roman Domination

In this section, we will discuss a two-sided bounded version of Extension
Roman Domination which was also suggested by a colleague of ours.

Problem name:  Bounded Extension Roman Domination, or bounded-ExtRD for short
Given:  A graph $G=\left(V,E\right)$ and functions $f,h\in\\{0,1,2\\}^{V}.$
Question:  Is there a minimal rdf $g\in\\{0,1,2\\}^{V}$ with $f\leq g\leq h$?

Namely, as we will show in 8.4, bounded-ExtRD is NP-complete. A standard way
to act in such circumstances is to look for FPT-algorithms. One natural
parameterization for this problem could be $\omega\left(2-h\right)$, because
for $2-h=0$, i.e., $\omega(2-h)=0$, we are back to ExtRD as a special case,
which is known to be solvable in polynomial time. Hence, this parameterization
can be viewed as a ‘distance-from-triviality’ parameter [GuoHufNie2004].
However, as we will prove in Theorem 8.1, this parameterization strategy
fails. We employ the well-known $\textsf{W}[1]$-completeness of Independent
Set, parameterized by the size of the solution, in the reduction presented in
the proof of Theorem 8.1. In that theorem, we actually discuss a slightly
different parameterization, namely
$\kappa_{h^{-1}(0)}(G,f,h)\coloneqq|h^{-1}(0)|$.

######  Theorem 8.1.

$\kappa_{h^{-1}(0)}$-bounded-ExtRD is $\textsf{W}[1]$-hard even on bipartite
graphs.

######  Proof 8.2.

Let $G=(V,E)$ be a graph and $k\in\mathbb{N}$. Define
$G^{\prime}=(V^{\prime},E^{\prime})$ with

$\begin{split}V^{\prime}\coloneqq&\,\\{a,b\\}\cup\\{w_{e},u_{e,x},u_{e,y}\mid
e=\\{x,y\\}\in E\\}\cup\\{r_{i}\mid i\in\left[k\right]\\}\cup\\{s_{v}\mid v\in
V\\}\\\ &\cup\\{v_{i},t_{v,i}\mid v\in V,i\in\left[k\right]\\},\\\
E^{\prime}\coloneqq&\,\\{\\{u_{e,x},w_{e}\\},\\{u_{e,y},w_{e}\\},\\{u_{e,x},x_{i}\\},\\{u_{e,y},y_{i}\\}\mid
e=\\{x,y\\}\in E,i\in\left[k\right]\\}\\\
&\cup\\{\\{t_{v,i},s_{v}\\},\\{t_{v,j},v_{i}\\},\\{a,v_{i}\\},\\{r_{i},v_{i}\\}\mid
v\in V,\,i,j\in\left[k\right],\,i\neq j\\}\cup\\{\\{a,b\\}\\}.\end{split}$

$t_{v,1}$$t_{v,i-1}$$t_{v,i+1}$$t_{i}$$t_{v,k}$$b$$a$$v_{i}$$r_{i}$$s_{v}$⋮⋮
(a) Construction for $v\in V$ and $i\in[k]$.

$y_{1}$$y_{k}$$x_{1}$$x_{k}$$u_{e,x}$$u_{e,y}$$w_{e}$⋮⋮ (b) Construction for
$e=\\{x,y\\}\in E$.

Figure 1: Gadgets for Theorem 8.1

1(a) and 1(b) gives an idea of how parts of the graph could look like.
Furthermore, we need the maps $f,h\in\\{0,1,2\\}^{V^{\prime}}$ with $f(z)=2$
for $z\in\\{a\\}\cup\\{w_{e}\mid e\in E\\}\cup\\{s_{v}\mid v\in V\\}$,
$f(z)=0$ otherwise, and $h(z)=0$ for $z\in\\{r_{i}\mid i\in[k]\\}$, $h(z)=2$
otherwise.

Since $f(a)=2$, all vertices in $\\{v_{i}\mid i\in[k],\,v\in V\\}$ are
dominated, as well as $a,b$. For each $e=\\{x,y\\}\in E$, $w_{e}$ dominates
$w_{e},u_{e,x},u_{e,y}$. Furthermore, $s_{v},t_{v,1},\ldots,t_{v,k}$ are
dominated by $s_{v}$ for $v\in V$. This leaves to dominate the set
$\\{r_{i}\mid i\in[k]\\}$. As the neighborhoods are pairwise disjoint, for
each $i\in[k]$, exactly one vertex $v_{i}\in N(r_{i})=\\{v_{i}\mid v\in V\\}$
must have the value $2$ in a rdf $g$ with $f\leq g$. This also implies that
$f(z)=g(z)$ for all $z\in V^{\prime}\setminus\\{v_{i}\mid i\in[k],\,v\in
V\\}$, as $z$ would not have a private neighbor (or $h(z)=0$).

######  Claim 2.

There is an independent set $I$ of size $k$ if and only if there exists a
minimal rdf $g$ on $G^{\prime}$ with $f\leq g\leq h$.

######  Proof 8.3 (Proof of the claim).

Let $I=\\{p^{1},\ldots,p^{k}\\}$ be an independent set with $p^{i}\neq p^{j}$
for $i,j\in[k]$ with $i\neq j$. Define $g:\>V^{\prime}\rightarrow\\{0,1,2\\}$
with

$z\mapsto\begin{cases}2,&z\in\\{a\\}\cup\\{w_{e}\mid e\in E\\}\cup\\{s_{v}\mid
v\in V\\}\cup\\{p^{i}_{i}\mid i\in[k]\\}\\\ 0,&\text{otherwise}\end{cases}.$

With the argument above, $g$ is a rdf. Furthermore, $f\leq g\leq h$ holds.
Assume $g$ is not minimal. As $g$ is a rdf and there exists no $z\in
V^{\prime}$ with $g(z)=1$, there has to be a $z\in V^{\prime}$ such that
$N(z)\setminus N[g^{-1}(2)\setminus\\{z\\}]$ empty. Since $p^{i}\neq p^{j}$
for $i,j\in[k]$ with $i\neq j$, $t_{p^{i},i}$ is a private neighbor of
$s_{p^{i}_{i}}$. For each $i\in[k]$, $r_{i}$ is a private neighbor of
$p^{i}_{i}$. Furthermore, $b$ is only dominated by $a$. Assume there exists an
$e=\\{x,y\\}\in E$ such that $w_{e}$ has no private neighbor but itself. This
implies $u_{e,x}$ and $u_{e,y}$ are dominated by some
$p^{j}_{j}\in\\{x_{i}\mid i\in[k]\\}\cap f^{-1}(2)$ and
$p^{l}_{l}\in\\{x_{i}\mid i\in[k]\\}\cap f^{-1}(2)$. This contradicts the
independence of $I$. Therefore, $g$ is a minimal.

To show the converse, let $g$ be a minimal rdf on $G^{\prime}$ with $f\leq
g\leq h$. As mentioned before, $g^{-1}(2)\setminus
f^{-1}(2)=\\{d^{1}_{1},\ldots,d^{k}_{k}\\}$ where $d^{i}\in V$ for $i\in[k]$.
Define $I=\\{d^{1},\ldots,d^{k}\\}$. Assume there exist $i,j\in[k]$ with
$i\neq j$ and $d^{i}=d^{j}$. $N(s_{d^{i}})\subseteq
N(\\{d^{i}_{i},d^{j}_{i}\\})$ implies that $g$ was not minimal in the first
place. To show that $I$ is independent, we assume there exist $d^{i},d^{j}\in
I$ such that $\\{d^{i},d^{j}\\}=e\in E$. This contradicts minimality, as
$w_{e}$ has no private neighbor but itself ($u_{e,d^{i}}\in N(d^{i})$ and
$u_{e,d^{j}}\in N(d^{j})$). Therefore, $I$ is an independent set of size $k$.
$\Diamond$

This concludes the proof of the validity of the reduction. Clearly, the
reduction can be computed in polynomial time. $G^{\prime}$ is also bipartite
with the classes $A=\\{a\\}\cup\\{u_{e,x}\mid x\in e\in
E\\}\cup\\{t_{v,i},r_{i}\mid v\in V,\,i\in[k]\\}$ and
$B=\\{b\\}\cup\\{w_{e}\mid e\in E\\}\cup\\{s_{v},v_{i}\mid v\in
V,\,i\in[k]\\}$. These classes can be checked in the definition of $E$, as in
each edge the vertex of $A$ is mentioned first and the vertex of $B$ is
mentioned second.

Since this reduction is also a polynomial-time reduction and since membership
in NP is easily seen using guess-and-check, we can conclude:

######  Corollary 8.4.

bounded-ExtRD is NP-complete, even on bipartite graphs.

Since $h$ maps no vertex to $1$ in the reduction presented in the proof of
Theorem 8.1, bounded-Ext-RDF is $\textsf{W}[1]$-hard, parameterized by
$\kappa_{2-h}(G,f,h)\coloneqq\sum_{v\in V}(2-h(v))$. Namely, in the
construction of Theorem 8.1,
$\kappa_{2-h}(G,f,h)=2\cdot\kappa_{|h^{-1}(0)|}(G,f,h)$.

Another parameterization could be $\omega\left(f\right)$: If
$\omega\left(f\right)=0$, there is a minimal rdf $g\in\\{0,1,2\\}^{V}$ with
$f\leq g\leq h$ if and only if $h$ is a rdf (this can be checked in polnomial
time). If there exists such a $g$, then $h$ is also a rdf. If $h$ is a rdf,
then we can decrease the value of the vertices until we can no longer decrease
the value of any vertices without losing the rdf property.

To understand the complexity of this parameter, we need the following
extension version of Hitting Set.

Problem name: Extension Hitting Set, or ExtHS for short Given:  A simple
hypergraph $H=\left(X,S\right)$, $S\subseteq 2^{X}$, and a set $U\subseteq X$.
Question:  Is there a minimal hitting set $T\subseteq X$ with $U\subseteq T$?

In [BlaFLMS2019], it was proven that ExtHS is $\textsf{W}[3]$-complete when
parameterized by $|U|$.

######  Theorem 8.5.

bounded-ExtRD is $\textsf{W}[3]$-hard on split graphs when parameterized by
the weight $\omega(f)$ of the lower-bound function $f$.

######  Proof 8.6.

Let $(X,S,U)$ with $X=\\{x_{1},\ldots,x_{n}\\}$,
$S=\\{S_{1},\ldots,S_{m}\\}\subseteq 2^{X}$ and $U\neq\emptyset$ be an
instance of ExtHS. Define $G=(V,E)$ with

$\begin{split}V&\coloneqq\\{c_{1},\ldots,c_{n}\\}\cup\\{t_{1},\ldots,t_{m}\\},\\\
E&\coloneqq\\{\\{c_{i},t_{j}\\}\mid x_{i}\in
S_{j}\\}\cup\binom{\\{c_{1},\ldots,c_{n}\\}}{2}.\end{split}$

Obviously, $G$ is a split graph. Let $T\coloneqq\\{t_{1},\ldots,t_{m}\\}$,
$C\coloneqq\\{c_{1},\ldots,c_{n}\\}$ and $\varphi:X\to C,x_{i}\mapsto c_{i}$.
Define the functions $f,h\in V^{\\{0,1,2\\}}$ with $f(t)=f(c)=h(t)=0$,
$f(u)=h(c)=h(u)=2$, for $u\in\varphi(U),\,t\in T,\,c\in C\setminus\varphi(U)$.
This implies $\sum_{v\in V}f(v)=2\cdot|U|.$ Notice that $f(v)=2$ if and only
if $\varphi^{-1}(v)\in U$.

Let $H$ be a minimal hitting set with $U\subseteq H$. Define

$g_{H}:V\rightarrow\\{0,1,2\\},x\rightarrow\begin{cases}0,&x\in
T\cup\\{c_{i}\in C\mid x_{i}\notin H\\}\\\ 2,&x\in\\{c_{i}\in C\mid x_{i}\in
H\\}=\varphi(H)\end{cases}.$

$U\subseteq H$ and $g_{H}(T)=\\{0\\}$ imply $f(v)\leq g_{H}(v)\leq h(v)$ for
each $v\in V$. Since $U$ is not empty, $g_{H}$ already dominates $C$. As $H$
is a hitting set, for each $s_{j}\in S$, there exists an $x_{i}\in S_{j}\cap
H$. Therefore, for each $t_{j}\in T$, there exists a $c_{i}\in N(t_{j})$ with
$g_{H}(c_{i})=2$. Hence, $g_{h}$ is a rdf. Assume there exists a $c_{i}\in C$
with $g_{H}(c_{i})=2$ such that $g_{H}-\chi_{\\{c_{i}\\}}$ is also a rdf. This
implies that for each $t_{j}\in N(c_{i})$ there exists a $c_{q}\in
N(t_{j})\cap g_{H}^{-1}(2)$. Hence, for each $s_{j}\in S$ with $x_{i}\in
s_{j}$, there exists an $x_{q}\in(s_{j}\cap H)\setminus\\{x_{i}\\}$. This
contradicts the minimality of $H$. Therefore, $g_{H}$ is a minimal rdf. Thus,
$(G,f,h)$ is a yes-instance of bounded-ExtRD if $(X,S,U)$ is a yes-instance of
ExtHS.

Let $g$ be a minimal rdf on $G$ with $f\leq g\leq h$. Define
$H_{g}=\varphi^{-1}(C\cap g^{-1}(2))=\\{x_{i}\mid c_{i}\in C\land
g(c_{i})=2\\}$. $U$ is a subset of $H_{g}$, as $f(v)\leq g(v)$ holds for each
$v\in V$. Since $g(t_{j})=0$ for each $t_{j}\in T$, there has to exist a
$c_{i}\in N(t_{j})$ such that $g(c_{i})=2$. Therefore, $H_{g}$ is a hitting
set. Assume there exists an $x_{i}\in H_{g}$ such that for each $S_{j}\in S$
with $x_{i}\in S_{j}$ there exists an $x_{q}\in H_{g}\subseteq S_{j}$.
Therefore, for each $t_{j}\in N(x_{i})\cap T$, there is a $c_{q}\in
N(t_{i})\setminus\\{x_{i}\\}$ with $g(c_{q})=2$. The existence of such a
$c_{q}$ implies that the private neighbor of $c_{i}$ cannot be in $C$. This is
a contradiction to the minimality of $g$. Thus, $(X,S,U)$ is a yes-instance of
ExtHS if $(G,f,h)$ is a yes-instance of bounded-ExtRD.

Since this reduction is also a polynomial-time reduction and since membership
in NP is easily seen using guess-and-check, we can conclude:

######  Corollary 8.7.

bounded-ExtRD is NP-complete on split graphs.

######  Remark 8.8.

This result is interesting, as we can show that Extension Dominating Set is
polynomial-time solvable on split graphs. As mentioned above, Ext RD can be
solved in polynomial time but Ext DS is NP-complete. Now we have a graph class
for which bounded-Ext RD is NP-complete but there is a polynomial-time
algorithm for Ext DS.

Our last proof would also work if $T$ would be a clique. This change does not
affect the proof, as $h(t)=0$ holds for each $t\in T$. The resulting graph is
then co-bipartite. Hence, we can state the following results.

######  Corollary 8.9.

bounded-ExtRD is NP-complete on co-bipartite graphs. bounded-ExtRD is
$\textsf{W}[3]$-hard on co-bipartite graphs when parameterized by the weight
$\omega(f)$ of the lower-bound function $f$.

We will make use of the parameterized reduction of Theorem 8.5 in the next
section, when we turn to discuss the (parameterized) complexity of Ext RHF.
The reductions provided there will also show that bounded-ExtRD, parameterized
by the weight of the lower-bound function, belongs to $\textsf{W}[3]$.
Therefore, the $\textsf{W}[3]$-hardness results proved in this section turn
into $\textsf{W}[3]$-completeness results.

Finally, let us mention that, in any given bounded-ExtRD instance $(G,f,h)$,
we can always assume (1) $f\leq h$ and, moreover, (2) $h(v)=0$ implies
$h(u)=2$ for some $u\in N(v)$. Otherwise, there cannot exist a rdf $g$ with
$f\leq g\leq h$. In particular, if $h(v)=0$, as $g\leq h$, then also $g(v)=0$,
and as $g$ should be a rdf, $g(u)=2$ for some $u\in N(v)$, so that $h(u)=2$ as
$g\leq h$. Both conditions are easy to check.

##  9 Complexity of Extension-Roman Hitting Function I

In this section, we will show that there are also instances of Roman Hitting
Function which are NP-complete and $\textsf{W}[3]$-complete, considering their
standard parameterizations. For the $\textsf{W}[3]$-membership, we make use of
the problem Multicolored Independent Family (MultIndFam) that is defined next.

Problem name: Multicolored Independent Family
Given:  A $(k+1)$-tuple $(S_{1},\ldots,S_{k},T)$ of subsets of $2^{U}$ on the
common universe $U$, i.e., $(U,S_{1}),\dots,(U,S_{k}),(U,T)$ are $k+1$ many
simple hypergraphs. Question:  Are there hyperedges $s_{1}\in
S_{1},\ldots,s_{k}\in S_{k}$ such that no $t\in T$ is a subset of
$\bigcup_{i=1}^{k}s_{i}\subseteq U$?

This problem is known to be $\textsf{W}[3]$-complete when parameterized by
$k\in\mathbb{N}$ (see [BlaFLMS2019, BlaFLMS2022]). As there are no good
canonical $\textsf{W}[3]$-complete parameterized problems, we use a reduction
to MultIndFam to prove membership in $\textsf{W}[3]$. Unfortunately, this
reduction is quite technical.

######  Theorem 9.1.

standard-Extension Roman Hitting Function is in $\textsf{W}[3]$.

######  Proof 9.2.

Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a (not necessarily simple) hypergraph
with correspondence $\tau:X\to I$ and let $f:X\to\\{0,1,2\\}$ be function,
comprising an instance of standard-Extension Roman Hitting Function. $(*)$ We
can assume that there are not two elements $x,y\in X$ such that $f(x)=f(y)=1$
with $\tau(x)=\tau(y)$ or $f(x)=2,f(y)=1$ with $x\in s_{\tau(y)}$. Otherwise,
we could use Corollaries 6.13 and 6.15.

We are going to construct an equivalent instance of MultIndFam next. To this
end, we define its universe as

$U\coloneqq X\cup\\{r_{i,x},x^{\prime}\mid x\in f^{-1}(\\{1,2\\}),i\in
I\\}\cup\\{\tau_{x}\mid x\in f^{-1}(1)\\}\,.$

For the construction of the hypergraphs, we need to define some additional
(auxiliary) sets:

  * •

For $x\in f^{-1}(\\{1,2\\})$, $i\in\mathbf{I}(x)$ abbreviate
$\tilde{s}_{x,i}\coloneqq s_{i}\cup\\{r_{i,x},x^{\prime}\\}$.

  * •

Define $t_{i}\coloneqq s_{i}\cup\\{\tau_{x}\mid x\in f^{-1}(1)\cap s_{i}\\}$
for $i\in I$ such that $\tau^{-1}(i)$ and $s_{i}\cap f^{-1}(2)$ are empty.

  * •

For each $x\in f^{-1}(2)$, let
$S_{x}\coloneqq\\{\tilde{s}_{x,i}\mid\tau(x)\neq i\\}$ and
for each $x\in f^{-1}(1)$, let
$S_{x}\coloneqq\\{s_{\tau(x)}\cup\\{\tau_{x}\\}\\}\cup\\{\tilde{s}_{x,i}\mid\tau(x)\neq
i\\}$.

  * •

Furthermore, we need the target set $T=T^{\prime}\cup T^{\prime\prime}$, where

$\begin{split}T^{\prime}\coloneqq\,\,&\\{\,t_{i}\mid i\in
I\land\tau^{-1}(i)=\emptyset\land s_{i}\cap
f^{-1}(2)=\emptyset\,\\}\quad\text{and}\\\
T^{\prime}\coloneqq\,\,&\left\\{\,\\{r_{i,x},y^{\prime}\\}\mid i\in
I\land\\{x,y\\}\subseteq(s_{i}\cap f^{-1}(\\{1,2\\}))\land x\neq
y\,\right\\}\\\ &\cup\left\\{\,\\{\tau_{x},y^{\prime}\\}\mid x\in
g^{-1}(1)\land y\in s_{\tau(x)}\land x\neq y\,\right\\}\,.\end{split}$

Now we will explain the idea of each element. It is important to keep in mind
that we want to use Theorem 6.17: If $x^{\prime}$ is in a chosen hyperedge,
then we assign the value 2 to $x$ in the minimal rhf. The element $r_{i,x}$
gives us information about the mapping $\rho$. $r_{i,x}$ is in one of the
chosen edges if and only if $\rho(x)=i$ holds. Therefore, the sets
$\\{r_{i,x},y^{\prime}\\}$ verify the Constraint 2 of Theorem 6.17. $\tau_{x}$
will only be in a set we chose if we assign the value 1 to $x$. Hence,
Constraint 3 will be checked by the sets $\\{\tau_{x},y\\}$. The sets in
$T^{\prime}$ correspond to the sets which we consider in Constraint 4. This is
also the reason why $\tau_{x}$ is in included in $t_{i}$. Since there exists a
$\tau_{x}$, $f(x)=1$. If $x\in R_{2}$, $s_{i}\cap R_{2}\neq\emptyset$. In the
MultIndFam instance, this corresponds to: $\tau_{x}$ will not be in our sets,
which implies that $t_{i}$ will not be covered completely.

######  Claim 3.

$(H,\tau,f)$ is a yes-instance of Ext RHF if and only if $(U,(S_{x})_{x\in
f^{-1}(\\{1,2\\})},T)$ is a yes-instance of the Multicolored Independent
Family problem..

######  Proof 9.3 (Proof of the claim).

First assume that $(H,\tau,f)$ is a yes-instance of Ext RHF, i.e., we have to
show that $(U,(S_{x})_{x\in f^{-1}(\\{1,2\\})},T)$ is a yes-instance of
MultIndFam. To prove this, we will use Theorem 6.17, keeping the observation
$(*)$ in mind. As $(H,\tau,f)$ is a yes-instance of Ext RHF, there exist a set
$f^{-1}(2)\subseteq R_{2}\subseteq f^{-1}(\\{1,2\\})$ and a mapping
$\rho:R_{2}\to I$ that fulfill all four constraints of Theorem 6.17. For each
$x\in R_{2}$, choose some $\tilde{s}_{x,\rho(x)}\in S_{x}$, and for each $x\in
f^{-1}(1)\setminus R_{2}$, choose $s_{\tau(x)}\cup\\{\tau_{x}\\}\in S_{x}$. We
will show that this choice of hyperedges from $(S_{x})_{x\in
f^{-1}(\\{1,2\\})}$ proves that $(U,(S_{x})_{x\in f^{-1}(\\{1,2\\})},T)$ is a
yes-instance of MultIndFam. For the sake of contradiction, assume that there
exists a hyperedge in $T$ which is a subset of

$\mathcal{S}\coloneqq\left(\bigcup_{x\in
R_{2}}\tilde{s}_{x,\rho(x)}\right)\cup\left(\bigcup_{x\in f^{-1}(1)\setminus
R_{2}}s_{\tau(x)}\cup\\{\tau_{x}\\}\right)\,.$

Observe that, for each $x\in f^{-1}(\\{1,2\\})$, $x^{\prime}\in\mathcal{S}$ if
and only if there is an $i\in\mathbf{I}(x)$ such that $\tilde{s}_{x,i}$ was
chosen. Therefore, $x$ has to be in $R_{2}$.

If there would exist a hyperedge in $T^{\prime\prime}$ which is in included in
$\mathcal{S}$, this would contradict Constraints 1 or 2. Now, consider a
hyperedge $t_{i}$ in $T^{\prime}$. Hence, we have some $i\in I$ with
$t_{i}\subseteq\mathcal{S}$, $s_{i}\cap f^{-1}(2)=\emptyset$ and
$\tau^{-1}(i)=\emptyset$. This implies that

$s_{i}\subseteq\left(\bigcup_{x\in f^{-1}(1)\setminus
R_{2}}s_{\tau(x)}\right)\cup\left(\bigcup_{x\in R_{2}}s_{\rho(x)}\right)\,.$

Furthermore, $f^{-1}(1)\cap R_{2}\cap s_{i}=\emptyset$, as otherwise, there
exists a $\tau_{x}\in t_{i}$, which is not in $\mathcal{S}$. This would
contradict the Constraint 4. Hence, $(U,(S_{x})_{x\in f^{-1}(\\{1,2\\})},T)$
is a yes-instance.

For the if-part, let $q_{x}\in S_{x}$ for each $x\in f^{-1}(\\{1,2\\})$ be a
solution for the MultIndFam instance, i.e., their union does not contain any
hyperedge from $T$. Define

$R_{2}\coloneqq f^{-1}(2)\cup\\{x\in f^{-1}(1)\mid\tau_{x}\notin q_{x}\\}$

and, for each $x\in R_{2}$, determine $\rho(x)$ such that
$\tilde{s}_{x,\rho(x)}=q_{x}$. We again use Theorem 6.17 and the four
constraints mentioned in this characterization theorem. Constraint 1 is
fulfilled by the construction of $R_{2}$. The next two constraints are met, as
otherwise a set of $T^{\prime\prime}$ would be included in $\bigcup_{x\in
f^{-1}(\\{1,2\\})}q_{x}$. Assume there exists a $j\in I$ with
$\tau^{-1}(j)=\emptyset$ and

$s_{j}\subseteq\left(\bigcup_{x\in f^{-1}(1)\setminus
R_{2}}s_{\tau(x)}\right)\cup\left(\bigcup_{x\in R_{2}}s_{\rho(x)}\right)\,.$

As for each $i\in I$, $t_{i}$ is no subset of $\bigcup_{x\in
f^{-1}(\\{1,2\\})}q_{x}$, there must be some $\tau_{x}\in t_{i}$, with $x\in
f^{-1}(1)\cap s_{j}$, which is not in $\bigcup_{x\in f^{-1}(\\{1,2\\})}q_{x}$.
Thus, $R_{2}\cap s_{i}\neq\emptyset.$ Hence, also Constraint 4 is met.
Therefore, $(H,f,\tau)$ is a yes-instance of Ext RHF. $\Diamond$

The following two claims are easy to prove but needed to conclude the proof.

######  Claim 4.

Given an instance of Ext RHS, the equivalent instance of MultIndFam as
described above can be constructed in polynomial time.

######  Claim 5.

The parameter $k$ of the constructed instance of MultIndFam is bounded by the
cardinality of $f^{-1}(\\{1,2\\})$ and hence by the weight of $f$, which is
the standard parameter of the original instance of Ext RHF.

Hence, Ext RHF belongs to $\textsf{W}[3]$.

As mentioned in the previous proof, the described reduction is also a
polynomial-time reduction. Therefore, Extension Roman Hitting Function is a
member of NP, but this is also (easily) observed by the guess-and-check
characterization of NP. For the hardness results, we will use bounded-
Extension Roman Domination as described in the previous section.

######  Theorem 9.4.

standard-Extension Roman Hitting Function is $\textsf{W}[3]$-hard even if the
correspondence function is injective.

######  Proof 9.5.

We will make use of Theorem 8.5, reducing from bounded-ExtRD. Let $(G,f,h)$ be
a instance of the bounded-ExtRD, with $G=(V,E)$. We can assume (1) $f\leq h$
and, moreover, (2) $h(v)=0$ implies $h(u)=2$ for some $u\in N(v)$. We
parameterize by $\omega(f)$. For $v\in X\coloneqq V\setminus h^{-1}(0)$,
define $T_{v}\coloneqq\left(N(v)\setminus
h^{-1}(\\{0,1\\})\right)\cup\\{v\\}$, and for $v\in h^{-1}(0)$, define
$T_{v}\coloneqq\left(N(v)\setminus h^{-1}(\\{0,1\\})\right)$. Further, we set
$\hat{S}\coloneqq(T_{v})_{v\in V}$ and we define $\tau$ as the correspondence
satisfying $\tau(v)=v$ and we let
$\overline{f}:X\rightarrow\\{0,1,2\\},\,v\mapsto f(v)$, i.e.,
$\overline{f}=f|_{X}$. Let $H=(X,\hat{S})$. Then, $(H,\tau,\overline{f})$
describes an instance of Ext RHF. The standard parameter is the weight of
$\overline{f}$ for this instance. As $f\leq h$, $h(v)=0$ implies $f(v)=0$.
Therefore, $\omega(f)=\omega(\overline{f})$, so that the parameter value does
not change when moving from the bounded-ExtRD instance to the standard-
Extension Roman Hitting Function instance. Clearly, the described construction
can be carried out in polynomial time. Trivially, the correspondence $\tau$ is
injective. What remains to be shown is that the construction enjoys the
reduction property, mapping yes-instances to yes-instances and no-instances to
no-instances.

Let $g$ be a minimal rdf on $G$ with $f\leq g\leq h$. Define
$\overline{g}:X\rightarrow\\{0,1,2\\},\,v\mapsto g(v)$, i.e.,
$\overline{g}=g|_{X}$. Thus, $\overline{f}\leq\overline{g}$. Let $v\in V$. For
$g(v)\in\\{1,2\\}$, $T_{v}$ is hit by $v$. If $g(v)=0$ holds, there has to
exist a $w\in N(v)$ with $g(w)=2$. This $w$ hits $T_{v}$. Therefore,
$\overline{g}$ is a rhf. Assume $\overline{g}$ is not minimal. Since $\tau$ is
injective, Constraint  ‣ 6.10 of Theorem 6.10 is satisfied. Hence, either
Constraint 1, Constraint 2, or the minimality of Constraint 3 of Theorem 6.10
has to be contradicted. If Constraint 1 is contradicted, this implies the
existence of $v,w\in V$ with $g(v)=\overline{g}(v)=2$,
$g(w)=\overline{g}(w)=1$ and $v\in T_{w}=\left(N(w)\setminus
h^{-1}(\\{0,1\\})\right)\cup\\{w\\}\subseteq N[w]$. This contradicts the
minimality of $g$, as we can set $g(w)=0$ and still have a rdf.

Consider Constraint 2. Assume there exists a $v\in\overline{g}^{-1}(2)$ such
that for each $w\in V\setminus\\{v\\}$,
$T_{w}\cap\overline{g}^{-1}(2)\neq\\{v\\}$ holds. Thus, for each $w\in N(v)$
there exists a $u\in(T_{w}\cap
N[w]\cap\overline{g}^{-1}(2))\setminus\\{v\\}\subseteq(N[w]\cap
g^{-1}(2))\setminus\\{v\\}$. This would imply that $g$ is not minimal.

Concerning Constraint 3, consider $\mathcal{T}\coloneqq\\{T_{v}\mid v\in
V,\tau^{-1}(v)\cap\overline{g}^{-1}(1)=\emptyset\\}=\\{(N(v)\cap
h^{-1}(2))\cup\\{v\\}\mid v\in V,\overline{g}(v)\neq 1\\}$. If
$\overline{g}(v)=2$, then $v$ trivially hits $(N(v)\cap
h^{-1}(2))\cup\\{v\\}$. If $\overline{g}(v)=0$, then for some $w\in N(v)$,
$g(w)=2$, as $g$ is a rdf of $G$. If $g(w)=2$, then $h(w)=2$, so that then $v$
hits $(N(v)\cap h^{-1}(2))\cup\\{v\\}$. Hence, $\overline{g}^{-1}(2)$ is a
hitting set of $\mathcal{T}$. Assume that there exists some
$z\in\overline{g}^{-1}(2)$ such that $\overline{g}^{-1}(2)\setminus\\{z\\}$ is
also a hitting set of $\mathcal{T}$. Hence, for each $T_{v}\in\cal T$ with
$z\in T_{v}$, there is some $y\in\overline{g}^{-1}(2)\setminus\\{z\\}$ with
$y\in T_{v}$. If $v=z$, then $y\in(N(v)\cap h^{-1}(2))$. Hence, $h(y)=2$ and
hence $\overline{g}(y)=2$. As $y\in N(z)$ in this case, we could set $g(z)=0$,
possibly leading to a smaller rdf. Now assume $v\neq z$. Then, $z\in(N(v)\cap
h^{-1}(2))$. Consider $y\in T_{v}$. If $y=v$, we can again argue that we may
set $g(z)=0$, possibly leading to a smaller rdf, because we found some $y\in
N(z)$ with $g(y)=2$. If $y\neq v$, then $\\{y,z\\}\subseteq(N(v)\cap
h^{-1}(2))$. As $h(v)=2$ implies $g(v)=2$, also in this third case, we can set
$g(z)=0$. In summary, in each case, we can find a rdf for $G$ that is smaller
than $g$ by setting $g(z)=0$. This contradicts the minimality of $g$. By
Theorem 6.10, $\overline{g}$ is minimal.

Let $\overline{g}$ be a minimal rhf, a solution to the instance
$(H,\tau,\overline{f})$. Define

$g:\>V\rightarrow\\{0,1,2\\},v\mapsto\begin{cases}\overline{g}(v),&v\in
X\text{, i.e., }h(v)\neq 0\\\ 0,&v\notin X\text{, i.e., }h(v)=0\end{cases}\,.$

As $\overline{g}$ extends $\overline{f}$, we have
$\overline{f}\leq\overline{g}$. By construction, $f\leq h$, so that $f(v)=0$
for $v\notin X$. Hence, $f\leq g$. Consider some $y\in h^{-1}(1)$. We show
that then, $g(y)\leq 1$, which proves $g\leq h$. Since $y\in h^{-1}(1)$, $y$
is only contained in the set $T_{y}=T_{\tau(y)}$ among all sets in $\hat{S}$.
If $g(y)=2$, i.e., $\overline{g}(y)=2$, this would contradict Theorem 6.10,
Constraint 2. We now prove that $g$ is a rdf. Consider some $v\in
g^{-1}(0)=\overline{g}^{-1}(0)\cup h^{-1}(0)$. If $v\in h^{-1}(0)$, there has
to exist a $u\in\overline{g}^{-1}(2)\cap T_{v}\subseteq g^{-1}(2)\cap N[v]$,
as there is no $u\in X$ with $\tau(u)=v$. If $v\in\overline{g}^{-1}(0)$, there
is no vertex in $\tau^{-1}(v)\cap\overline{g}^{-1}(1)$, as $\tau(v)=v$.
Therefore, there exists a $u\in\overline{g}^{-1}(2)\cap T_{v}\subseteq
g^{-1}(2)\cap N[v]$.

Next, we argue why $g$ is minimal. Assume there exist $v,w\in V$ with
$\overline{g}(v)=g(v)=2$, $\overline{g}(w)=g(w)=1$ and $\\{v,w\\}\in E$,
violating the first property of Theorem 2.4. This would contradict the
minimality of $\overline{g}$, as $v\in\left(N(w)\setminus
h^{-1}(\\{0,1\\})\right)\cup\\{w\\}=T_{w}$, because $g(v)=2$ implies $h(v)=2$
by $g\leq h$. Assume that there exists a $v\in g^{-1}(2)=\overline{g}^{-1}(2)$
with $N[v]\setminus N[g^{-1}(2)\setminus\\{v\\}]\subseteq\\{v\\}$, violating
the privacy property of Theorem 2.4. This implies that, for each $w\in N(v)$,
there is a $t\in(N[w]\cap\overline{g}^{-1}(2))\subseteq(N(w)\setminus
h^{-1}(\\{0,1\\}))\cup\\{w\\}$ with $t\neq v$. This contradicts Constraint 2
of Theorem 6.10. Consider $G^{\prime}\coloneqq G\left[g^{-1}(0)\cup
g^{-1}(2)\right]$. As $g$ is a rdf, $D\coloneqq g^{-1}(2)$ is a dominating set
of $G^{\prime}$. If $D$ is not a minimal dominating set (hence violating the
last constraint of Theorem 2.4), then there must be some $v$ with $g(v)=2$
such that $D\setminus\\{v\\}$ is also a dominating set. Hence, for each $u\in
N[v]$, there is some $v_{u}\in N[u]\cap(D\setminus\\{v\\})$. By construction,
for each such $v_{u}$, we have $g(v_{u})=2$ and hence
$\overline{g}(v_{u})=h(v_{u})=2$ and $T_{v_{u}}\neq\\{v_{u}\\}$ (*). On the
other hand, as $\overline{g}$ is a minimal rhf, by the last constraint of
Theorem 6.10, $D=g^{-1}(2)=\overline{g}^{-1}(2)$ is a minimal hitting set of
$\mathcal{T}\coloneqq\\{T_{x}\mid x\in V\setminus\overline{g}^{-1}(1)\\}$. As
$T_{x}\subseteq N[x]$ for all $x\in V$, $(D\setminus\\{v\\})$ is not only a
dominating set of $G^{\prime}$ but also a hitting set of $\mathcal{T}$ because
of (*), contradicting mininality as stated in Theorem 6.10. As all possible
violations of the characterization for minimal rdf as formulated in of Theorem
2.4 have been shown to contradict our assumptions, we must conclude that $g$
is indeed a minimal rdf.

As this is also a polynomial-time reduction, it implies following corollary.

######  Corollary 9.6.

Extension Roman Hitting Function is NP-complete.

##  10 Complexity of Extension-Roman Hitting Function II

We know already that Extension Roman Hitting Function is polynomial-time
solvable if the correspondence function is surjective. Since Extension Roman
Hitting Function with injective correspondence function is as hard as the
general Hitting Set problem, this leads to the question if
$\kappa_{1}(\mathcal{I})=|\\{i\in I|\tau^{-1}(i)=\emptyset\\}|$ could be a
good parameter for this problem for each instance $\mathcal{I}=(H,\tau,f)$
with $H=(V,(s_{i})_{i\in I})$, $\tau:V\to I$, $f:V\to\\{0,1,2\\}$, somehow
measuring the _distance from triviality_ again. In other words, we try to use
parameterized complexity as a way to study the phenomenon that classical
function properties as surjectivity seem to be crucial for finding polynomial-
time algorithms for Extension Roman Hitting Function.

######  Theorem 10.1.

$\kappa_{1}$-Extension Roman Hitting Function is $\textsf{W}[1]$-hard.

For the proof we use the fact that the reduction in the proof of Theorem 9.4
is also a FPT-reduction from $\kappa_{1}$-Extension Roman Hitting Function to
$\kappa_{h^{-1}(0)}$-bounded-ExtRDF, with
$\kappa_{h^{-1}(0)}(G,f,h)\coloneqq|h^{-1}(0)|$.

######  Lemma 10.2.

$\kappa_{1}$-Extension Roman Hitting Function, $\kappa_{h^{-1}(0)}$-bounded-
Ext-RDF, $\kappa_{2-h}$-bounded-Ext-RDF${}\in\textsf{XP}$.

######  Proof 10.3.

For $\kappa_{1}$-Extension Roman Hitting Function and
$\kappa_{h^{-1}(0)}$-bounded-Ext-RDF, it is enough to show that
$\kappa_{1}$-$\textsc{Ext-RHF}\in\textsf{XP}$. Let $(H,\tau,f)$ be an instance
with $H=(X,\hat{S})$, $\hat{S}=(s_{i})_{i\in I}$. This XP-algorithm is not
difficult, as we branch over each index in $\\{i\in
I\mid\tau^{-1}(i)=\emptyset\>\\}$ and try to hit the edge $s_{i}$ with an
element from $X$. If each edge is hit, we check with Algorithm 2 if there
exists a minimal rhf which is bigger than this function. If Algorithm 2
returns yes, we also can return yes. Otherwise, we try another way to hit all
the edges in $S\setminus\tau(X)$. This algorithm does run in time
$\mathcal{O}(n^{\kappa_{1}(H,\tau,f)})$.

Now we consider $\kappa_{2-h}$-bounded-Ext-RDF. Let $(G,f,h)$ be an instance
with $G=(V,E)$ with $f\leq h$. First we want to set $g(x)\coloneqq 2$ for each
vertex $x\in N(f^{-1}(2))\cap f^{-1}(1)$. However, if the set
$N(f^{-1}(2))\cap f^{-1}(1)\cap h^{-1}(\\{0,1\\})$ is non-empty, we face a
trivial no-instance, as for the solution $g$ we are looking for, any vertex
$x$ with $f(x)=2$ satisfies $g(x)=2$ and moreover, a vertex $y\in N(x)$ with
$f(y)=1$ must be set to $2$ by $g$, which is ruled out if $h(y)\in\\{0,1\\}$.
As $f\leq g\leq h$, we can set $g(x)\coloneqq 1$ for $x\in f^{-1}(1)\cap
h^{-1}(1)$. After these settings, the XP-algorithm branches on each vertex in
$h^{-1}(0)$ and tries to dominate it by a neighbor in $h^{-1}(2)\setminus
N(f^{-1}(1)\cap h^{-1}(1))$. As $2\cdot|h^{-1}(0)|\leq\omega\left(2-h\right)$,
in total we have at most $n^{\frac{\omega\left(2-h\right)}{2}}$ possibilities
to do this. After each of these possible settings for $g$, where we define
$g(x)\coloneqq f(x)$ for any hitherto undefined vertex $x$, we run the
polynomial-time algorithm for Ext-RDF from [AbuFerMan2022b], with $g$ as the
lower-bound function. This algorithm will work, as each vertex in $h^{-1}(0)$
is dominated (the undominated vertices are the ones which are set to $1$) and
there is no vertex in $N(f^{-1}(2))\cap f^{-1}(1)\cap h^{-1}(1)$.

We are discussing several other parameterizations in the following that either
lead to para-NP-hardness results (in Theorem 10.4) or to FPT-results (in
Theorem 10.10). The parameterization function is denoted by $\kappa_{Y}$,
where $Y$ specifies a subset of the universe $X$ of the instance
$(X,\hat{S},f)$, such that $\kappa_{Y}(X,\hat{S},f)=|Y|$.

######  Theorem 10.4.

$\kappa_{\zeta}$-Extension Roman Hitting Function is para-NP-hard for each
parameterization described by
$\zeta\in\\{f^{-1}(0),f^{-1}(1),f^{-1}(2),f^{-1}(\\{0,2\\})\\}$.

######  Proof 10.5.

For all the reductions that we show in this proof, we use the NP-completeness
of Extension Hitting Set. Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a hypergraph
with $U\subseteq X$, $I\cap X=\emptyset$ and an element $a,i_{b},i_{c}\notin
X\cup I$. We define $X^{\prime}=X\cup\\{a\\}$, $I^{\prime}\coloneqq I\cup X$
and $I^{\prime\prime}=I\cup X\cup\\{i_{b},i_{c}\\}$. For each
parameterization, we prove that even if the parameter takes values zero or one
and is hence fixed, each of the obtained problems can be used to solve
arbitrary instances of Extension Hitting Set.

First, we discuss $\zeta=f^{-1}(0)$. Define the hypergraph
$H^{\prime}=(X,\hat{S^{\prime}}=(s_{i}^{\prime})_{i\in I^{\prime}})$.
Furthermore, we need $\tau:X\to I^{\prime},x\mapsto x$, and for $i\in
I^{\prime}$, we set

$s_{i}^{\prime}\coloneqq\begin{cases}s_{i},&i\in I\\\ \\{i\\},&i\in
X\end{cases}\quad\text{and}\quad
f:X\to\\{0,1,2\\},x\mapsto\begin{cases}2,&x\in U\\\ 1,&x\in X\setminus
U\end{cases}.$

This implies $|f^{-1}(0)|=0$, i.e., the parameter value is constant.

######  Claim 6.

$(H,U)$ is a yes-instance of Extension Hitting Set if and only if
$(H^{\prime},\tau,f)$ is a yes-instance of Extension Roman Hitting Function.

######  Proof 10.6 (Proof of the claim).

First, we assume there is a minimal rhf $g$ on $H^{\prime},\tau$ with $f\leq
g$. Let $D=g^{-1}(2)$. As $\tau(i)=\emptyset$ for each $i\in I$, $s_{i}\cap D$
is not empty and $D$ a hitting set. If there exists an $x\in D$ such that for
each $i\in\mathbf{I}(x)$, there is a $y\in s_{i}\cap(D\setminus\\{x\\})$, then
this would contradict Constraint 2 of Theorem 6.10. Hence, $D$ is a minimal
hitting set.

Assume there is a minimal hitting set $D\subseteq X$ on $H$ with $U\subseteq
D$. Define $g:X\to\\{0,1,2\\}$ with $g^{-1}(2)=D$ and $g^{-1}(1)=X\setminus
D$. Trivially, $f\leq g$ holds. We will use Theorem 6.10 to show that $g$ is a
minimal rhf. The definition of $\tau$ implies the correctness of the first two
constraints, i.e., Constraints  ‣ 6.10 and 1. As $D$ is a minimal hitting set
on $H$ and each hyperedge of $H$ is also a hyperedge of $H^{\prime}$,
Constraint 2 also holds. The remaining constraint holds as
$X=f^{-1}(\\{1,2\\})=\tau(f^{-1}(\\{1,2\\}))$ and $D$ is a minimal hitting set
on $H$. By Theorem 6.10, $g$ is a minimal rhf. $\Diamond$

Next, we take a look at the parameter described by $|f^{-1}(1)|$. Define the
hypergraph $H^{\prime\prime}=(X^{\prime},(s_{i}^{\prime\prime})_{i\in
I^{\prime\prime}})$. Furthermore, we need

$\tau^{\prime}:X^{\prime}\to I^{\prime\prime},x\mapsto\begin{cases}x,&x\in
X\\\ i_{b},&x=a\end{cases},\quad
s_{i}^{\prime\prime}\coloneqq\begin{cases}s_{i},&i\in I\\\ \\{a,i\\},&i\in
X\\\ X^{\prime},&i=i_{b}\\\ \\{a\\},&i=i_{c}\\\ \end{cases}$

for $i\in I^{\prime\prime}$. Define $f^{\prime}:X^{\prime}\to\\{0,1,2\\}$ with
$f^{\prime-1}(2)=U\cup\\{a\\}$ and $f^{-1}(0)=X\setminus U$. Thus
$|f^{\prime-1}(1)|=0$, i.e., the parameter value is constant.

######  Claim 7.

$(H,U)$ is a yes-instance of Extension Hitting Set if and only if
$(H^{\prime\prime},\tau^{\prime},f^{\prime})$ is a yes-instance of Extension
Roman Hitting Function.

######  Proof 10.7 (Proof of the claim).

First, we assume that there is a minimal rhf $g$ on $H^{\prime\prime},\tau$
with $f^{\prime}\leq g$. Define $D\coloneqq g^{-1}(2)\setminus\\{a\\}$. As
$\tau^{\prime-1}(i)=\emptyset$ for each $i\in I$, $s_{i}\cap D$ is not empty
and $D$ a hitting set on $H$. If there exists a $x\in D$ such that for each
$i\in\mathbf{I}(x)$ there is a $y\in s_{i}\cap(D\setminus\\{x\\})$, then it
would contradict Constraint 2 of Theorem 6.10. Hence $D$ is a minimal hitting
set.

Assume there is a minimal hitting set $D\subseteq X$ on $H$ with $U\subseteq
D$. Define $g:\\{0,1,2\\}^{X}$ with $g^{-1}(2)=D\cup\\{a\\}$ and
$g^{-1}(0)=X\setminus D$. Trivially, $f^{\prime}\leq g$ holds. We will use
Theorem 6.10 to show that $g$ is a minimal rhf. Since $g^{-1}(1)$ is empty,
the first two constraints, i.e., Constraints  ‣ 6.10 and 1, are fulfilled. As
$D$ is a minimal hitting set on $H$ and each hyperedge of $H$ is also a
hyperedge of $H^{\prime}$, Constraint 2 also holds. For the last constraint we
have to consider $i\in I$, only, since $g(a)=2$. From the fact that $D$ is a
minimal hitting set on $H$ and $s^{\prime\prime}_{i_{c}}$ is only hit by $a$,
the last constraint of Theorem 6.10 follows. Thus, $g$ is a minimal rhf.
$\Diamond$

The cardinality $|f^{-1}(2)|$ describes the next parameter that we will
consider. We will reuse $H^{\prime\prime}$ and $\tau^{\prime}$. Furthermore,
we need

$f^{\prime\prime}:X^{\prime}\to\\{0,1,2\\},x\mapsto\begin{cases}2,&x=a\\\
1,&x\in U\\\ 0,&x\in X\setminus U\end{cases}.$

Thus, $|f^{\prime\prime-1}(2)|=1$, i.e., the parameter value is constant.

######  Claim 8.

$(H,U)$ is a yes-instance of Extension Hitting Set if and only if
$(H^{\prime\prime},\tau^{\prime},f^{\prime\prime})$ is a yes-instance of
Extension Roman Hitting Function.

######  Proof 10.8 (Proof of the claim).

We use 6.13 exhaustively. This implies
$(H^{\prime\prime},\tau^{\prime},f^{\prime\prime})$ is a yes-instance of
Extension Roman Hitting Function if and only if
$(H^{\prime\prime},\tau^{\prime},\tilde{f})$ with $\tilde{f}(x)=2$ for $x\in
U\cup\\{a\\}$ and $\tilde{f}(x)=0$ for $x\in X\setminus U$ is a yes-instance.
Since $\tilde{f}=f^{\prime}$, this case follows by the last one. $\Diamond$

The last case is the parameter $\kappa_{\zeta}$ with
$\zeta=f^{-1}(\\{0,2\\})$. Define the hypergraph
$H^{\prime\prime\prime}=(X^{\prime},(s_{i}^{\prime\prime\prime})_{i\in
I^{\prime\prime}})$. Again, we reuse $\tau^{\prime}$. Furthermore, we need

$f^{\prime\prime\prime}:X^{\prime}\to\\{0,1,2\\},x\mapsto\begin{cases}2,&x=a\\\
1,&x\in X\end{cases},\quad
s_{i}^{\prime\prime\prime}\coloneqq\begin{cases}s_{i},&i\in I\\\
\\{a,i\\},&i\in U\\\ \\{i\\},&i\in X\setminus U\\\ X^{\prime},&i=i_{b}\\\
\\{a\\},&i=i_{c}\\\ \end{cases}$

for $i\in I^{\prime}$. This implies $|f^{\prime\prime\prime-1}(\\{0,2\\})|=1$,
i.e., the parameter value is constant.

######  Claim 9.

$(H,U)$ is a yes-instance of Extension Hitting Set if and only if
$(H^{\prime\prime\prime},\tau^{\prime},f^{\prime\prime\prime})$ is a yes-
instance of Extension Roman Hitting Function.

######  Proof 10.9 (Proof of the claim).

First, we use 6.13 exhaustively. This implies that
$(H^{\prime\prime\prime},\tau^{\prime},f^{\prime\prime\prime})$ is a yes-
instance of Extension Roman Hitting Function if and only if
$(H^{\prime\prime\prime},\tau^{\prime},\tilde{f})$ with $\tilde{f}(x)=2$ for
$x\in U\cup\\{a\\}$ and $\tilde{f}(x)=1$ for $x\in X\setminus U$ is a yes-
instance of Extension Roman Hitting Function. Assume there is a minimal rhf
$g$ on $H^{\prime\prime\prime}$, $\tau^{\prime}$ with $\tilde{f}\leq g$.
Define $D=g^{-1}(2)\setminus\\{a\\}$. As $a\notin s_{i}^{\prime}=s_{i}$ for
each $i\in I$ (i.e., $\tau^{\prime-1}(i)=\emptyset$), $s_{i}\cap D$ is not
empty for such an $i$. If there existed a $x\in D$ such that for each
$i\in\mathbf{I}(x)$ there is a $y\in s_{i}\cap(D\setminus\\{x\\})$, then this
would contradict Constraint 2 of Theorem 6.10. Hence, $D$ is a minimal hitting
set.

Assume that there is a minimal hitting set $D\subseteq X$ on $H$ with
$U\subseteq D$. Define $g\in\\{0,1,2\\}^{X^{\prime}}$ with $g(x)=2$ for $x\in
D\cup\\{a\\}$ and $g(x)=1$ for $x\in X\setminus D$. As before, we use Theorem
6.10 to show that $g$ is a minimal rhf. Since $s_{\tau(x)}=\\{x\\}$ for each
$x\in g^{-1}(1)=X\setminus D\subseteq X\setminus U$, the two first constraints
hold. The fact that $D$ is a minimal hitting set on $H$ and $s_{i_{c}}\cap
g^{-1}(2)=\\{a\\}$ imply Constraint 2. Constraint 3 follows, because $D$ is a
hitting set on $H$ and the hyperedges $(s_{i}^{\prime\prime\prime})_{i\in
I^{\prime\prime}\setminus I}$ are hit by $\\{a\\}\cup(X\setminus D)$.
Therefore, $g$ is a minimal rhf of $H^{\prime\prime\prime}$. $\Diamond$

This finishes the discussion of all parameters.

######  Theorem 10.10.

$\kappa_{\zeta}$-$\textsc{Extension Roman Hitting Function}\in\textsf{FPT}$
for $\zeta=\omega\left(2-f\right)$ and $\zeta=f^{-1}(\\{0,1\\})\\}$.

######  Proof 10.11.

To show this result, we will construct a simple FPT-algorithm. Let
$(H=(X,\hat{S}),\tau,f)$ be an instance. The idea is to walk through all
functions $g\in\\{0,1,2\\}^{X}$ with $f\leq g$ and test if $g$ is a minimal
rhf. This runs in FPT-time, as for vertices $x\in X$ with $f(x)=0$ there are 3
choices, for $f(x)=1$ there are 2 choices and for $f(x)=2$ there is only 1
choice. Furthermore, we can check in polynomial time if a function is a
minimal rhf (such an algorithm can be constructed by simply modifying
Algorithm 2). Therefore, there are

$\displaystyle\left(\prod_{x\in f^{-1}(0)}3\right)\cdot\left(\prod_{x\in
f^{-1}(1)}2\right)$ $\displaystyle\leq$ $\displaystyle\left(\prod_{x\in
f^{-1}(0)}2^{2-f(x)}\right)\cdot\left(\prod_{x\in f^{-1}(1)}2^{2-f(x)}\right)$
$\displaystyle=$ $\displaystyle 2^{\omega\left(2-f(x)\right)}$

or

$\displaystyle\left(\prod_{x\in f^{-1}(0)}3\right)\cdot\left(\prod_{x\in
f^{-1}(1)}2\right)$ $\displaystyle\leq$ $\displaystyle\left(\prod_{x\in
f^{-1}(0)}3\right)\cdot\left(\prod_{x\in f^{-1}(1)}3\right)$ $\displaystyle=$
$\displaystyle 3^{|f^{-1}(\\{0,1\\})|}$

many possibilities for $g$.

##  11 Enumerating Minimal Roman Hitting Sets

Now we want to enumerate all minimal Roman hitting sets. We do this by
constructing a branching algorithm. Let $H=(X,\hat{S}=(s_{i})_{i\in I})$ be a
hypergraph. We construct a set $X^{\prime}\subseteq X$ which will include all
vertices that are already in $R_{2}$, i.e., $R_{2}\subseteq X^{\prime}$, or at
least can be in $R_{2}$. To do this, we need the tuple $(R_{1},R_{2})$, where
$R_{1}\subseteq I$ includes all indices and $R_{2}\subseteq X^{\prime}$
includes all elements which are a part of the rhs that we are going construct.
In the branching process, we will either put an $x\in X^{\prime}$ into $R_{2}$
or _delete $x$_, which describes the following operation: remove $x$ from
$X^{\prime}$ and then also remove $x$ from all the hyperedges that it belonged
to. Therefore, we can consider the hypergraph

$H^{\prime}:=(X^{\prime},(s_{i}\cap X^{\prime})_{i\in I})$

as describing the ‘current hypergraph’ during the computation process.
However, we will modify the hyperedges $s_{i}$ during the computation, so that
always $s_{i}\subseteq X^{\prime}$ is satisfied, but in terms of the original
hyperedge $s_{i}$, we can always think of $s_{i}\cap X^{\prime}$ as the
current counterpart.

We define $I^{\prime}=I\setminus(R_{1}\cup\mathbf{I}(R_{2}))$ as the set of
indices from $I$ that describe edges that are not yet hit. This also defines a
new function $\mathbf{I^{\prime}}$. If we _add an $i\in I^{\prime}$ to
$R_{1}$_ (as a further operation), we will also delete all $x\in s_{i}$ from
$X^{\prime}$, as these vertices cannot be in a minimal rhs if $i$ is also.

Our measure is given by

$\mu\coloneqq\mu(X^{\prime},\hat{S}^{\prime},R_{1},R_{2})\coloneqq|X^{\prime}\setminus
R_{2}|+|I^{\prime}|\,.$

Initially, we have $X^{\prime}=X$, $I^{\prime}=I$ and $R_{2}=\emptyset$, so
that $\mu=|X|+|I|$ at the beginning. As our main result of this section, we
are going to show that all minimal rhs can be enumerated in
$\mathcal{O}^{*}\left(\sqrt[3]{3}^{|X|+|I|}\right)$ time with polynomial
delay. We also provide an example hypergraph family showing that there cannot
be any significantly better enumeration algorithm, as a hypergraph with $n$
vertices and $m$ indices from this family has at least $\sqrt[3]{3}^{n+m}$
many minimal rhs.

Before each branching step, we check if there is a minimal rhs $(P_{1},P_{2})$
on $H^{\prime}$ with $(R_{1},R_{2})\leq(P_{1},P_{2})$ and try to use a
reduction rule. Among all applicable branching rules, we will use the rule
with the smallest number. First, we define some reduction rules that are
always tried before the branching rules.

######  Reduction Rule 1.

If there is an $x\in X^{\prime}\setminus R_{2}$ with
$\mathbf{I}(x)\subseteq\mathbf{I}(R_{2})$, then delete $x$.

This reduction rule is sound, as if we would put such a vertex into a rhs that
includes $R_{2}$, then it cannot be minimal by Theorem 4.5.

######  Reduction Rule 2.

If there is an $i\in I^{\prime}$ with $s_{i}=\emptyset$, then put $i$ into
$R_{1}$.

The soundness of this rule follows easily, since $i$ has to be hit.

######  Branching Rule 1.

Let $i\in I^{\prime}$ with $s_{i}=\\{x\\}\subseteq X^{\prime}\setminus R_{2}$.
Then we branch as follows:

  1. 1.

Add $i$ to $R_{1}$ and delete $x$.

  2. 2.

Add $x$ to $R_{2}$.

######  Lemma 11.1.

The case distinction of Branching Rule 1 is complete. The worst-case branching
vector is $(2,2)$.

######  Proof 11.2.

Since $s_{i}$ only includes $x$, $i\in R_{1}$ or $x\in R_{2}$ must hold. Both
$i\in R_{1}$ and $x\in R_{2}$ is impossible by Constraint 1 of Theorem 4.5.
Therefore, we delete $x$ and then add $i$ to $R_{1}$ by Reduction Rule 2, or
we put $x$ into $R_{2}$. In both cases, the measure decreases by two, as $i$
is no longer in $I^{\prime}$ and $x$ is deleted from $X^{\prime}$ or put into
$R_{2}$.

######  Branching Rule 2.

Let $x\in X^{\prime}$ with $|\mathbf{I^{\prime}}(x)|\geq 3$. Then we branch as
follows:

  1. 1.

Add $x$ to $R_{2}$.

  2. 2.

Delete $x$.

######  Lemma 11.3.

The case distinction of Branching Rule 2 is complete. The worst-case branching
vector is $(4,1)$.

######  Proof 11.4.

In this branching scenario, we branch if $x$ is part of the solution or not.
Trivially, this is a complete case distinction. By adding $x$ to $R_{2}$, the
measure decreases by at least 4, as the resulting $I^{\prime}$ does not
contain any hyperedge which includes $x$. The decrease in the other case is
trivially one.

######  Branching Rule 3.

Let $x,y\in X^{\prime}$ with $\mathbf{I^{\prime}}(x)=\\{i\\}$ and
$s_{i}=\\{x,y\\}$. Then we branch as follows:

  1. 1.

Add $x$ to $R_{2}$ and delete $y$.

  2. 2.

Add $y$ to $R_{2}$ and delete $x$.

  3. 3.

Add $i$ to $R_{1}$ and delete $x$ and $y$.

######  Lemma 11.5.

The case distinction of Branching Rule 3 is complete. The worst-case branching
vector is $(3,3,3)$.

######  Proof 11.6.

This is a complete case distinction, as $x$ and $y$ cannot be in the same
minimal rhs $P=(P_{1},P_{2})$ with $R_{1}\subseteq P_{1}\subseteq I$ and
$R_{2}\subseteq P_{2}\subseteq X^{\prime}$. If there exists such a minimal
rhs, then $R_{2}\setminus\\{x\\}$ is also a hitting set on
$\left(s_{i}\right)_{i\in I\setminus R_{2}}$, which contradicts Constraint 2
of Theorem 4.5. As in each case, $i$ is no longer in $I^{\prime}$ and $x$ and
$y$ are no longer in $X^{\prime}\setminus R_{2}$, the measure reduces by 3.

######  Branching Rule 4.

Let $x\in X^{\prime}$ with $\mathbf{I^{\prime}}(x)=\\{i\\}$ with $|s_{i}|\geq
3$. Then we branch as follows:

  1. 1.

Add $x$ to $R_{2}$ and delete the remaining vertices in $s_{i}$.

  2. 2.

Delete $x$.

######  Lemma 11.7.

The case distinction of Branching Rule 4 is complete. The worst-case branching
vector is $(4,1)$.

######  Proof 11.8.

Analogously to 11.5, $x$ cannot be in $R_{2}$ if there is another vertex in
$R_{2}\cap s_{i}$. Therefore, we can delete the other vertices in $s_{i}$, $i$
is not in $I^{\prime}$ anymore and the measure is dreasing by 4. The other
case holds trivially.

######  Remark 11.9.

From now on, we can assume that $|\mathbf{I^{\prime}}(x)|=2$. This is seen as
follows.
If $|\mathbf{I^{\prime}}(x)|>2$, Branching Rule 2 would trigger.
For $|\mathbf{I^{\prime}}(x)|=0$ we would use Reduction Rule 1.
The branching rules 1, 3 and 4 handle the case $|\mathbf{I^{\prime}}(x)|=1$,
distinguishing cases for $\mathbf{I^{\prime}}(x)=\\{i\\}$ concerning
$|s_{i}|$.

We will use this fact for the analysis of the following branching rules.

######  Branching Rule 5.

Let $x,y\in X^{\prime}$ with $x\neq y$ and
$\mathbf{I^{\prime}}(x)=\mathbf{I^{\prime}}(y)$. Then we branch as follows:

  1. 1.

Add $x$ to $R_{2}$ and delete $y$.

  2. 2.

Add $y$ to $R_{2}$ and delete $x$ .

  3. 3.

Delete $x$ and $y$.

######  Lemma 11.10.

The case distinction of Branching Rule 5 is complete. The worst-case branching
vector is $(4,4,2)$.

######  Proof 11.11.

There cannot exist a minimal rhs $(P_{1},P_{2})$ with $R_{1}\subseteq
P_{1}\subseteq I$ and $R_{2}\cup\\{x,y\\}\subseteq P_{2}\subseteq X^{\prime}$,
as $(P_{1},P_{2}\setminus\\{x\\})$ would also be a rhs. Therefore, this
branching gives a complete case distinction. In all three cases, $x$ and $y$
leave $X^{\prime}\setminus R_{2}$. In the first two cases, the indices in
$\mathbf{I^{\prime}}(x)$ are no longer in $I^{\prime}$.

######  Branching Rule 6.

Let $i\in I^{\prime}$ with $s_{i}=\\{x,y\\}$. Then we branch as follows:

  1. 1.

Add $x$ to $R_{2}$.

  2. 2.

Add $y$ to $R_{2}$ and delete $x$ .

  3. 3.

Add $i$ to $R_{1}$ and delete $x$ and $y$.

######  Lemma 11.12.

The case distinction of Branching Rule 6 is complete. The worst-case branching
vector is $(3,4,3)$.

######  Proof 11.13.