# On the Complexity of the Upper r-Tolerant Edge Cover Problem

Ararat Harutyunyan, Mehdi Khosravian Ghadikolaei, Nikolaos Melissinos, Jérôme Monnot, Aris Pagourtzis

► To cite this version:

Ararat Harutyunyan, Mehdi Khosravian Ghadikolaei, Nikolaos Melissinos, Jérôme Monnot, Aris Pagourtzis. On the Complexity of the Upper r-Tolerant Edge Cover Problem. 3rd International Conference on Topics in Theoretical Computer Science (TTCS), Jul 2020, Tehran, Iran. pp.32-47, 10.1007/978-3-030-57852-7_3 . hal-03165379

HAL Id: hal-03165379

https://inria.hal.science/hal-03165379

Submitted on 10 Mar 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the complexity of the upper *r*-tolerant edge cover problem

Ararat Harutyunyan¹, Mehdi Khosravian Ghadikolaei¹, Nikolaos Melissinos¹, Jérôme Monnot¹, and Aris Pagourtzis²

¹ Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016 Paris, France, {mehdi.khosravian-ghadikolaei,ararat.harutyunyan,jerome.monnot}@dauphine.fr
nikolaos.melissinos@dauphine.eu

² School of Electrical and Computer Engineering, National Technical University of Athens, Polytechnioupoli, 15780 Zografou, Athens, Greece, pagour@cs.ntua.gr

**Abstract.** We consider the problem of computing edge covers that are tolerant to a certain number of edge deletions. We call the problem of finding a minimum such cover **r-TOLERANT EDGE COVER (r-EC)** and the problem of finding a maximum minimal such cover **UPPER r-EC**. We present several **NP-hardness** and inapproximability results for **UPPER r-EC** and for some of its special cases.

**Key words:** Upper Edge Cover, Matching, **NP-completeness**, Approximability

## 1 Introduction

In this paper we define and study *tolerant edge cover problems*. An *edge cover* of a graph $G = (V, E)$ without isolated vertices is a subset of edges $S \subseteq E$ which covers all vertices of $G$, that is, each vertex of $G$ is an endpoint of at least one edge in $S$. The *edge cover number* of a graph $G = (V, E)$, denoted by $ec(G)$, is the minimum size of an edge cover of $G$ and it can be computed in polynomial time (see Chapter 19 in [29]). An edge cover $S \subseteq E$ is called *minimal* (with respect to inclusion) if no proper subset of $S$ is an edge cover. Minimal edge cover is also known in the literature as an *enclaveless set* [30] or as a *nonblocker set* [14]. While a minimum edge cover can be computed efficiently, finding the largest minimal *edge cover* is **NP-hard** [27], where it is shown that the problem is equivalent to finding a dominating set of minimum size. The associated optimization problem is called *upper edge cover* (and denoted **UPPER EC**) [1] and the corresponding optimal value will be denoted $uec(G)$ in this paper for the graph $G = (V, E)$.

Here, we are interested in minimal edge cover solutions tolerant to the failures of at most $r-1$ edges. Formally, given an integer $r \ge 1$, an edge subset $S \subseteq E$ of $G = (V, E)$ is a *tight r-tolerant edge-cover* (r-tec for short) if the deletion of any set of at most $r-1$ edges from $S$ maintains an edge cover<fnref n="3" /> and the deletion

<footnote n="3">³ It might be more intuitive to call such an edge cover $(r-1)$-tolerant, but for simplicity and due to the fact that each vertex has at least degree $r$ in the cover, we have chosen to use the term $r$-tolerant.</footnote>
of any edge from $S$ yields a set which is not a (tight) $r$-tolerant edge cover. Equivalently, we seek an edge subset $S$ of $G$ such that the subgraph $(V, S)$ has minimum degree $r$ and it is minimal with this property. For the sake of brevity we will omit the word 'tight' in the rest of the paper. Note that the case $r = 1$ corresponds to the standard notion of minimal edge cover.

As an illustrating example consider the situation in which the mayor of a big city seeks to hire a number of guards, from a security company, who will be constantly patrolling streets between important buildings. An $r$-tolerant edge cover reflects the desire of the mayor to guarantee that the security is not compromised even if $r - 1$ guards are attacked. Providing a maximum cover would be the goal of a selfish security company, who would like to propose a patrolling schedule with as many guards as possible, but in which all the proposed guards are necessary in the sense that removing any of them would leave some building not $r$-covered.

*Related work* UPPER EC has been investigated intensively during recent years, mainly using the terminologies of *spanning star forests* and *dominating sets*. A *dominating set* in a graph is a subset $S$ of vertices such that any vertex not in $S$ has at least one neighbor in $S$. The *minimum dominating set problem* (denoted MINDS) seeks the smallest dominating set of $G$ of value $\gamma(G)$. We have the equality $\text{uec}(G) = n - \gamma(G)$ [27].

Thus, using the complexity results known for MINDS, we deduce that UPPER EDGE COVER is NP-hard in planar graphs of maximum degree 3 [20], chordal graphs [6] (even in *undirected path graphs*, the class of vertex intersection graphs of a collection of paths in a tree), bipartite graphs, split graphs [5] and $k$-trees with arbitrary $k$ [12], and it is *polynomial* in $k$-trees with fixed $k$, convex bipartite graphs [13], strongly chordal graphs [16]. Concerning the approximability, an **APX**-hardness proof with explicit inapproximability bound and a combinatorial 0.6-approximation algorithm is proposed in [28]. Better algorithms with approximation ratio 0.71 and 0.803 are given respectively in [9] and [2]. For any $\varepsilon > 0$, UPPER EDGE COVER is hard to approximate within a factor of $\frac{259}{260} + \varepsilon$ unless $\mathbf{P=NP}$ [28]. The weighted version of the problem, denoted as UPPER WEIGHTED EDGE COVER, have been recently studied in [24], in which it is proved that the problem is not $O(\frac{1}{n^{1/2-\varepsilon}})$ approximable nor $O(\frac{1}{\Delta^{1-\varepsilon}})$ in edge weighted graphs of order $n$ and maximum degree $\Delta$.

Related notions of dominating sets are introduced in the literature under the name *r-tuple domination* [3, 18, 19, 21, 22, 25], and *r-domination* [8, 18]. A set $S \subseteq V$ is called a *r-tuple dominating set* of $G = (V, E)$ if for every vertex $v \in V$, $|N_G[v] \cap S| \ge r$. The minimum cardinality of a *r-tuple dominating set* of $G$ is called *r-tuple domination number* and usually denoted by $\gamma_{\times r}(G)$. The case $r = 2$ is often called the *double domination number* [21]. Complexity and approximation results on $\gamma_{\times r}(G)$ are given in [3, 25, 26] where it is proved that for any $r \ge 2$ fixed the problem is **APX**-complete in graphs of maximum degree $r+2$ [25], **NP**-hard in split graphs and bipartite graphs for any $r \ge 1$ [26] and it admits a **PTAS** for unit disk graphs [3]. Finally, the *upper r-tuple domination*
number^4 of a graph $G$ has been recently investigated in [7] where an upper bound
on this quantity for regular graphs is presented, with together a characterization
of extremal graphs achieving this upper bound depending on parameter $r$. The
particular case $r=1$, corresponding to the *upper domination number* (denoted
uds($G$) here but also known as $\Gamma(G)$), has been proved **NP**-hard in [10] and
extensively studied from complexity and approximability point of view in [4].

*Our contribution* In Section 3 we present several properties of *r-tec* solutions and of the *ec*<sub>*r*</sub> and *uec*<sub>*r*</sub> values in graphs. Furthermore, we give a characterization of *r-tec* solutions based on the *γ*(*G*) and *γ*<sub>2</sub>(*G*) values of graphs, where we have equality between *uec* and *uec*<sub>2</sub> values.

In Section 4, we provide several complexity results. More specifically, for the
DOUBLE UPPER EC we show that it is **NP**-hard in cubic planar graphs and
split graphs and for the general UPPER *r*-EC we show that it is **NP**-hard in
*r*-regular bipartite graphs. Furthermore, we show that the UPPER (*r* + 1)-EC is
**NP**-hard in graphs with maximum degree *Δ* + 1 if the UPPER *r*-EC is **NP**-hard
in graphs with maximum degree *Δ* (and this holds even for bipartite graphs).

In Section 5 we present some inapproximability results starting by proving
that, unless $\mathbf{P}=\mathbf{NP}$, UPPER EC is not approximable within $\frac{593}{594}$ in graphs of
max degree 4 and $\frac{363}{364}$ in graphs of max degree 5 (the previous known result was
for graphs with maximum degree 6). Furthermore, we present the first inapprox-
imability results for the DOUBLE UPPER EC for graphs with maximum degree
6 and 9.

## 2 Definitions

*Graph notation and terminology* Let $G = (V, E)$ be a graph and $S \subseteq V$; $N_G(S) = \{v \in V: \exists u \in S, vu \in E\}$ denotes the *neighborhood* of $S$ in $G$ and $N_G[S] = S \cup N_G(S)$ denotes the *closed neighborhood* of $S$. For singleton sets $S = \{s\}$, we simply write $N_G(s)$ or $N_G[s]$, even omitting $G$ if clear from the context. The *maximum degree* and *minimum degree* of a graph are denoted $\Delta(G)$ and $\delta(G)$ respectively. For a subset of edges $S$, $V(S)$ denotes the vertices that are incident to edges in $S$. A vertex set $U \subseteq V$ induces the graph $G[U]$ with vertex set $U$ and $e \in E$ being an edge in $G[U]$ iff both endpoints of $e$ are in $U$. If $S \subseteq E$ is an edge set, then $\bar{S} = E \setminus S$, edge set $S$ induces the graph $G[V(S)]$, while $G_S = (V, S)$ denotes the partial graph induced by $S$. In particular, $G_{\bar{S}} = (V, E \setminus S)$. Let also $\alpha(G)$ and $\gamma(G)$ denote the size of the largest independent and smallest dominating set of $G$, respectively.

An edge set $S$ is called *edge cover* if the partial graph $G_S$ is spanning and
it is a *matching* if $S$ is a set of pairwise non adjacent edges. An edge set $S$ is
*minimal* (resp., *maximal*) with respect to a graph property if $S$ satisfies the graph
property and any proper subset $S' \subset S$ of $S$ (resp., any proper superset $S' \supset S$
of $S$) does not satisfy the graph property. For instance, an edge set $S \subseteq E$ is a
maximal matching (resp., minimal edge cover) if $S$ is a matching and $S + e$ is

<footnote>^4 The maximum cardinality of a minimal *r*-tuple dominating set of *G*.</footnote>
not a matching for some $e \in \bar{S}$ (resp., $S$ is an edge cover and $S - e$ is not an edge cover for some $e \in \bar{S}$).

**Problem definitions** Let $G = (V, E)$ be a graph where the minimum degree is at least $r \ge 1$, i.e., $\delta(G) \ge r$. We assume $r$ is a constant fixed greater than one (but all results given here hold even if $r$ depends on the graph). A $r$-DEGREE EDGE-COVER $^5$ is defined as a subset of edges $G' = G_S = (V, S)$, such that each vertex of $G$ is incident to at least $r \ge 1$ distinct edges $e \in S$. As $r$-tolerant edge-cover (or simply $r$-tec) we will call an edge set $S \subseteq E$ if it is a minimal $r$-degree edge-cover i.e. if for every $e \in S$, $G' - e = (V, S \setminus \{e\})$ is not an $r$-degree edge-cover. Alternatively, $\delta(G') = r$, and $\delta(G' - e) = r - 1$. If you seek the minimization version, all the problems are polynomial-time solvable. Actually, the case of $r = 1$ corresponds to the edge cover in graphs. The optimization version of a generalization of $r$-EC known as the MIN LOWER-UPPER-COVER PROBLEM (MINLUCP), consists of, given a graph $G$ where $G = (V, E)$ and two non-negative functions $a, b$ from $V$ such that $\forall v \in V, 0 \le a(v) \le b(v) \le d_G(v)$, of finding a subset $M \subseteq E$ such that the partial graph $G_M = (V, M)$ induced by $M$ satisfies $a(v) \le d_{G_M}(v) \le b(v)$ (such a solution will be called a lower-upper-cover) and minimizing its total size $|M|$ among all such solutions (if any). Hence, an $r$-EC solution corresponds to a lower-upper-cover with $a(v) = r$ and $b(v) = d_G(v)$ for every $v \in V$. MINLUCP is known to be solvable in polynomial time even for edge-weighted graphs (Theorem 35.2 in Chapter 35 of Volume A in [29]). We are considering two associated problems, formally described as follows.

**$r$-EC**

**Input:** A graph $G = (V, E)$ of minimum degree $r$.

**Solution:** $r$-tec $S \subseteq E$ of $G$.

**Output:** Minimize $|S|$.

**UPPER $r$-EC**

**Input:** A graph $G = (V, E)$ of minimum degree $r$.

**Solution:** $r$-tec $S \subseteq E$ of $G$.

**Output:** Maximize $|S|$.

For a graph $G$, the optimal values of $r$-EC and UPPER $r$-EC will be denoted by $ec_r(G)$ and $uec_r(G)$ respectively. In particular, $ec_1(G) = ec(G)$ and $uec_1(G) = uec(G)$. As indicated above, $ec_r(G)$ can be computed in polynomial-time. In Fig 1, we illustrate the difference between the two problems $r$-EC and UPPER $r$-EC clearly for $r = 2$. Note that throughout the paper we will also use the term DOUBLE UPPER EC to refer to UPPER 2-EC.

An edge dominating set $S \subseteq E$ of a simple graph $G = (V, E)$ is a subset $S$ of edges such that for any edge $e \in E$ of $G$, at least one edge of $S$ is incident to

<footnote n="5">5 A different generalization of edge cover was considered in [17], requiring that each connected component induced by the edge cover solution contains at least $r$ edges. Clearly, if every vertex is incident to at least $r$ edges from the cover, then each connected component induced by the edge cover solution contains at least $r$ edges.</footnote>
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Graph $G = (V, E)$ with 6 vertices and 11 edges is shown in (a); (b) and (c) give a solution for 2-EC and DOUBLE UPPER EC of size 6 and 8 respectively.</figcaption></figure>

e. The EDGE DOMINATING SET problem (EDS in short) consists in finding an edge dominating set of minimum size; the optimal value of an edge dominating set is usually denoted $\text{eds}(G)$. EDS is known to be NP-hard in general graphs (problem [GT2] in [20]). It is well known that the problem is equivalent to solve the problem consisting of finding a maximal matching of $G$ with minimum size. According to standard terminology, this problem is also called lower matching (LOWER EM in short).

## 3 Basic properties of *r*-tolerant solutions

The next property presents a simple characterization of feasible *r*-tec solution generalizing the well known result given for minimal edge covers, i.e., 1-tec, affirming that $S$ is a 1-tec solution of $G$ if and only if $S$ is spanning and the subgraph $(V, S)$ induced by $S$ is $(K_3, P_4)$-free.

*Property 1.* Let $r \ge 1$ and let $G = (V, E)$ be a graph with minimum degree $\delta \ge r$. $S$ is an *r*-tec solution of $G$ if and only if the following conditions meet on $G_S = (V, S)$:

(1) $V = V_1(S) \cup V_2(S)$ where $V_1(S) = \{v \in V : d_{G_S}(v) = r\}$ and $V_2(S) = \{v \in V : d_{G_S}(v) > r\}$.

(2) $V_2(S)$ is an independent set of $G_S$.

*Proof.* Let $r \ge 1$ be a fixed integer and let $G = (V, E)$ be a graph instance of UPPER *r*-EC, i.e., a graph of minimum degree at least $r$. Let us prove the necessary conditions: if $S \subseteq E$ is an *r*-tec solution, then by construction, $V = V_1(S) \cup V_2(S)$ is a partition of vertices with minimum degree $r$ in $S$. Now, if $uv \in S$ with $u, v \in V_2(S)$, then $S - uv$ is also *r*-tec which is a contradiction of minimality.

Now, let us prove the other direction. Consider a subgraph $G' = (V, S)$ induced by edge set $S$ satisfying (1) and (2). By (1) it is clear $G_S$ has minimum
degree at least $r$. If $uv \in S$, then by (2) one vertex, say $u \in V_1(S)$ because $V_2(S)$ is an independent set. Hence, the deletion of $uv$ leaves $u$ of degree $r-1$ in the subgraph induced by $G_{S \setminus \{uv\}}$ and then $S$ is an $r$-tec solution. $\square$

**Property 2.** Let $r \ge 1$, for all graphs $G = (V, E)$ of minimum degree at least $r$, the following inequality holds:

$$2\mathrm{ec}_r(G) \ge \mathrm{uec}_r(G) \qquad (1)$$

*Proof.* For a given graph $G = (V, E)$ with $n$ vertices, let $S^*$ be an optimal solution of UPPER $r$-EC, that is $|S^*| = \mathrm{uec}_r(G)$. Let $(V_1^*, V_2^*)$ be the associated partition related to solution $S^*$ as indicated in Property 1. Using this characterization, we deduce $\mathrm{uec}_r(G) \le r|V_1^*| \le rn$. On the other side, if $G'$ denotes the subgraph induced by a minimum $r$-tec solution of value $\mathrm{uec}_r(G)$, we get $2\mathrm{ec}_r(G) = \sum_{v \in V} d_{G'}(v) \ge rn$. Combining these two inequalities, the results follows. $\square$

In particular, inequality (1) of Property 2 shows that any $r$-tec solution is a $\frac{1}{2}$-approximation of UPPER $r$-EC.

The next property is quite natural for induced subgraphs and indicates that the size of an optimal solution of a maximization problem does not decrease with the size of the graph. Nevertheless, this property is false in general when we deal with partial subgraphs; for instance, for the upper domination number, we get $\mathrm{uds}(K_3) = 1 < 2 = \mathrm{uds}(P_3)$. It turns out that this inequality is valid for the upper edge cover number.

**Property 3.** Let $G = (V, E)$ be a graph such that $0 < r \le \delta(G)$. For every partial subgraph $G' \subseteq G$ with $\delta(G') \ge r$, the following inequality holds:

$$\mathrm{uec}_r(G) \ge \mathrm{uec}_r(G') \qquad (2)$$

*Proof.* Fix an integer $r \ge 1$ and a graph $G = (V, E)$ with $\delta(G) \ge r$. Let $G' = (V', E')$ with $\delta(G') \ge r$ be a partial subgraph of $G$, i.e., $V' \subseteq V$ and $E' \subseteq E$. Consider an upper $r$-tec solution $S'$ of $G'$ with size $|S'| = \mathrm{uec}_r(G')$. We prove inequality (2) by starting from $S = S'$ and by iteratively repeating the following procedure:

1. Select a vertex $v \in V$ with $d_{G_S}(v) < r$ and $e = uv \in E \setminus S$.

2. If $u$ is covered less or more than $r$ times by $S$, then $S := S + e$.

3. If vertex $u$ is covered exactly $r$ times by $S$, consider two cases:

(a) If every vertex $u' \in N_{G_S}(u)$ has degree $d_{G_S}(u') \le r$, then $S := S + e$.

(b) Otherwise there exists a vertex $u' \in N_{G_S}(u)$ with $d_{G_S}(u') > r$ then $S := S + e - u'u$.

We repeat this process until every vertex of $G$ is covered at least $r$ times. Obviously, this algorithm terminates because $\sum_{v \notin V_2(S)} d_{G_S}(v)$ increase at each iteration where we recall $V_2(S) = \{v \in V : d_{G_S}(v) > r\}$. Since at each step, the size of $S$ never decreases, we only need to show that we end the process with a $r$-tec solution of the whole graph. In order to prove that, we will show by induction
that $V_2(S)$ is an independent set of $G_S$ for each iteration. Using Property 1, we get an r-tec solution because $V_1(S) = V \setminus V_2(S)$. Initially $V_2(S) = V_2(S')$ is an independent set of $G_S$ because $S'$ is a r-tec solution of $G'$. Assume it is true for iteration $k$ and consider iteration $k+1$. During step 2, $V_2(S)$ remains unchanged in both cases $d_{G_S}(u) < r$ or $d_{G_S}(u) > r$. So by induction the result is valid. During step 3.(a), $V_2(S) := V_2(S) + u$, but $V_2(S) \cap N_{G_S}(u) = \emptyset$; so $V_2(S)$ remains an independent set of $G_S$. During step 3.(b), $V_2(S)$ remains unchanged if $d_{G_S}(u') > r+1$, otherwise $V_2(S) := V_2(S) - u'$. Thus, $V_2(S)$ remains an independent set of $G_S$ by induction. In conclusion, $uec_r(G) \ge |S| \ge |S'| = \text{uec}_r(G')$ and the property holds. □

We can prove a similar property for the size of a partial solution and the upper edge cover number. More specifically, in a graph $G = (V, E)$ a partial r-tec defined as a set $S \subseteq E$ such that the set $V_2(S) = \{v \in V | d_{G_S}(v) > r\}$ is an independent set of $G_S$.

**Property 4.** Let $G = (V, E)$ be a graph such that $0 < r \le \delta(G)$. If $E' \subseteq E$ is a partial r-tec of $G$ then the following inequality holds:

$$ \text{uec}_r(G) \ge |E'| \quad (3) $$

The proof of the above property is similar to Property's 3 except that we will start with $S := E'$.

**Property 5.** Let $G = (V, E)$ and $E' \subseteq E$ be a solution for UPPER r-EC of $G$ then for any $1 \le m < r$ we can find a set $E'' \subseteq E'$ such that $E''$ is a m-tec of $G$. Especially, if $m = r-1$ then $E' \setminus E''$ is a tec of $G[V(E' \setminus E'')]$.

*Proof.* It is easy to find a m-tec of $G$ that is a subset of $E'$ if we start from the graph $G_{E'}$ which has minimum degree $r$. Any m-tec of $G_{E'}$ is a m-tec of $G$. Now, if $m = r-1$ and $G' = G[V(E' \setminus E'')]$ we will prove that $E' \setminus E''$ is a tec of $G'$. In order to do this, we need to show that the set $V_2 = \{v \in V | d_{G'_{E' \setminus E''}}(v) > 1\}$ is an independent set in $G'_{E' \setminus E''}$. Let $u, v \in V_2$ be two vertices which are connected in $G'_{E' \setminus E''}$ and they have degree greater than one. Then, because $E''$ is a $(r-1)$-tec of $G$, we know that the vertices $u$ and $v$ are covered $r-1$ so in $E'$ are covered at least $r+1$ times and they are connected. This is a contradiction because $E'$ is an a solution for UPPER r-EC. So, if $m = r-1$ then $E' \setminus E''$ is a tec of $G[V(E' \setminus E'')]$.
□

**Property 6.** Let $r \ge 1$. For all graphs $G = (V, E)$ of minimum degree at least $r$, the following inequality holds:

$$ \text{uec}_r(G) \le r \cdot \text{uec}(G) \quad (4) $$

*Proof.* Let $E_1 \subseteq E$ and $E_r \subseteq E$ be the solutions of UPPER EC and UPPER r-EC. By Property 5 we can have a set $E' \subseteq E$ such that $E'$ is a $(r-1)$-tec and $E_r \setminus E'$ is a TEC of $G[V(E_r \setminus E')]$. Then by Property 3 and because $E'$ is a $(r-1)$-tec we have that:

$$ \text{uec}_r(G) = |E'| + |E_r \setminus E'| \le \text{uec}_{r-1}(G) + \text{uec}(G) \quad (5) $$
Therefore, by induction to r we will show that $uec_r(G) \le r \cdot uec(G)$.

* Induction base: for $r = 2$ we have that $uec_2(G) \le 2uec(G)$.

* Induction hypothesis: for $0 < r' < \delta(G)$ we have $uec_{r'}(G) \le r' \cdot uec(G)$.

* Induction step: we will show that $uec_{r'+1}(G) \le (r' + 1) \cdot uec(G)$. The last can be proved using the inequality 5 and the induction hypothesis:

$$ uec_{r'+1}(G) \le uec_{r'}(G) + uec(G) \le r' \cdot uec(G) + uec(G) = (r' + 1) \cdot uec(G). \quad \square $$

A well known relation between the domination number and the upper edge cover number for any graph G with n vertices is the following:

$$ uec(G) = n - \gamma(G). $$

The previous equation can not be generalized for the r-domination number and the r upper edge cover number in any graph. However, we can prove the next relation.

**Property 7.** Let $r \ge 1$. For all graphs $G = (V, E)$ with n vertices and minimum degree at least r. The next inequality between $uec_r(G)$ and the r-domination number holds:

$$ uec_r(G) \ge r(n - \gamma_r(G)) $$

**Proof.** In order to prove this we will start from a minimum r-dominating set S and we will construct a partial r-tec of G. S dominates all the vertices in $V \setminus S$ at least r times so for each $v \in V \setminus S$ we can select $u_1, \dots, u_r \in S$ such that $vu_i \in E$, $\forall i = 1, \dots, r$ and we construct the set $E_v = \{vu_i | i = 1, \dots, r\}$. We will prove that the set $E' = \bigcup_{v \in V \setminus S} E_v$ is a partial r-tec. Recall that a subset $E'$ of edges is a partial r-tec if in the graph $G_{E'}$ the set $V_2 = \{v \in V | d_{G_{E'}} > r\}$ is an independent set. This property holds in our set because we selected the edges in order to be incident to at least one vertex of degree exactly r. So, by the Property 4 we have that $uec_r(G) \ge |E'|$. As for the size of $E'$ we observe that for each vertex $v \in V \setminus S$ we have used exactly r edges that are incident to a vertex of S and both of those sets ($V \setminus S$ and S) are independent in $G_{E'}$. So the size of $E'$ is equal to $r(n - |S|)$ which implies:

$$ uec_r(G) \ge |E'| = r(n - \gamma_r(G)) \quad \square $$

In the next lemma we are interested in graphs where the equality between uec and uec_r holds.

**Lemma 8.** Let $G = (V, E)$ be a graph such that $1 < r \le \delta(G)$, then the following are equivalent:

1. $\gamma_r(G) = \gamma(G)$

2. $uec_r(G) = r \cdot uec(G)$

**Proof.** Starting from a graph of order n were $\gamma_r(G) = \gamma(G)$ we will prove that $uec_r(G) = r \cdot uec(G)$. In this case we have that:

$$ r \cdot uec(G) = r \cdot (n - \gamma(G)) = r \cdot (n - \gamma_r(G)) \le uec_r \quad (\text{by Prop. 7}) $$
In addition, we have that $r \cdot \text{uec}(G) \ge \text{uec}_r(G)$ (by Prop. 6) so we proved that:

$$ \gamma_r(G) = \gamma(G) \implies \text{uec}_r = r \cdot \text{uec}. $$

For the converse, let $G = (V, E)$ be a graph such that $\text{uec}_r = r \cdot \text{uec}$, $E_r$ be a maximum r-tec and $E_1$ be a maximum tec. First suppose that there exists a partition of the vertices $V'_1 \cup V'_2 = V$ such that for all $v \in V'_1$ we have $d_{G_{E_r}}(v) = r$ and both of $V'_1, V'_2$ are independent in $G_{E_r}$. It is easy to see that $V'_2$ is a r-dominating set of G because $V'_1$ is independent in $G_{E_r}$ so each vertex of it is dominated at least r times by the vertices in $V'_2$. Therefore, because $V'_1, V'_2$ are independent in $G_{E_r}$ and for all $v \in V'_1$ we have $d_{G_{E_r}}(v) = r$ we can conclude that $|E_r| = r \cdot |V'_1|$. This gives us the following:

$$ \text{uec}_r(G) = |E_r| = r \cdot |V'_1| = r(n - |V'_2|) \le r(n - \gamma_r(G)). $$

Because in Prop. 7 we showed that $\text{uec}_r(G) \ge r(n - \gamma_r(G))$ we have that:

$$ r(n - \gamma_r(G)) = \text{uec}_r(G)r \cdot \text{uec} = r(n - \gamma(G)) $$

which implies that:

$$ \text{uec}_r = r \cdot \text{uec} \Rightarrow \gamma_r(G) = \gamma(G). $$

Thus, in order to complete the proof we have to show that when the values $\text{uec}$ and $\text{uec}_r$ of a graph are equal then we always have a partition as the one described in the above assumption. Assuming that there is no such partition then for any partition $V'_1, V'_2$ such that $V'_2$ is independent, all the vertices $v \in V'_1$ have degree $d_{G_{E_r}}(v) = r$ and $V'_1$ cannot be independent. First we will show that, for the previous partition, the following property holds:

$$ \text{if } v \in V'_1 \text{ then } N_{G_{E_r}}(v) \not\subseteq V'_1. $$

Starting from $V'_1 := V'_1(E_r)$ and $V'_2 := V'_2(E_r)$ (see Prop. 1) we have to remove vertices $u \in V'_1$ such that $N_{G_{E_r}}(v) \subseteq V'_1$ until we have the desired condition. So, we repeat the following:

1. Select a vertex $u \in V'_1$ such that $N_{G_{E_r}}(u) \subseteq V'_1$.

2. Set $V'_1 := V'_1 - u$ and $V'_2 := V'_2 + u$.

We have to show that the previous process terminates when the desired properties hold for $V'_1$ and $V'_2$. It is easy to see this holds because whenever we remove a $u \in V'_1$ vertex such that $N_{G_{E_r}}(u) \subseteq V'_1$ from it, we reduce, at least by one, the number of vertices with this property in $V'_1$. Therefore, the remaining vertices $u \in V'_1$ have $d_{G_{E_r}}(u) = r$ and the vertices in $V'_2$ are independent in $G_{E_r}$.

Now, due to the assumption, we know that $V'_1$ cannot be independent (in $G_{E_r}$) and for all $u \in V'_1$ we have $d_{G_{E_r}}(u) = r$. This observation combined with the fact that $V'_2$ is independent in $G_{E_r}$ gives $r \cdot |V'_1| > E_r$. Furthermore, because each vertex in $V'_1$ has at least one neighbor in $V'_2$ we can select one edge for each vertex of $V'_1$ adjacent to a vertex in $V'_2$. The set which consists of this edges is a partial tec of size $|V'_1|$ so by the Prop. 4 we have $\text{uec} \ge |V'_1|$. This gives us:

$$ E_r < r \cdot |V'_1| \le r \cdot \text{uec} $$

which is a contradiction because we have $\text{uec}_r = r \cdot \text{uec}$. $\square$
A known relation between the domination number and the r-domination number is:

$$ \gamma_r(G) \geq \gamma(G) + r - 2 $$

so, by the above relation and the lemma 10 we can conclude the following:

**Corollary 9.** There is no graph G such that $uec_r = r \cdot uec(G)$ for any $r \geq 3$.

Now, we will present some graphs where the equation $uec_2 = 2uec$ holds. It is easy to see that the smallest graph in which this relation holds is $C_4$. Conversely, we have the following lemma.

**Lemma 10.** For any graph $G = (V, E)$ with $|V| = n \geq 4$ if $uec_2(G) = 2uec(G)$ then $|E(G)| \leq \frac{n(n-2)}{2}$ when $n$ is even and $|E(G)| \leq \frac{n(n-2)-1}{2}$ when $n$ is odd.

*Proof.* By the lemma 8 we know that the eq. $uec_2(G) = 2uec(G)$ is equivalent to $\gamma_2(G) = \gamma(G)$. So, $\gamma(G)$ has to be greater than 2 and it deduces that the maximum number of edges in $G$ can not be greater than $\frac{n(n-2)}{2}$, and $\frac{n(n-2)-1}{2}$ in the even and odd cases respectively. □

We will now show that the above upper bounds are tight. Let $G = (V, E) = K_n$ be a clique of size $n$. First we construct a maximum matching $M \subseteq E$ of $G$; if $n$ is even then the graph $G_{\overline{M}}$ has $\gamma_2(G_{\overline{M}}) = \gamma(G_{\overline{M}})$ and the number of edges in $G_{\overline{M}}$ is equal to $\frac{n(n-1)}{2} - |M| = \frac{n(n-1)}{2} - \frac{n}{2} = \frac{n(n-2)}{2}$. In the case when $n$ is odd any maximum matching covers $n-1$ vertices. Let $v \in V$ be the vertex that is not covered by the matching $M$. Then the only dominating set of $G_{\overline{M}}$ of size one is the $\{v\}$. Therefore if we remove any edge incident to $v$, let $uv \in E$ be that edge, then in $G_{\overline{M}-uv}$ we have $\gamma_2(G_{\overline{M}-uv}) = \gamma(G_{\overline{M}-uv})$ and the number of edges in $G_{\overline{M}-uv}$ are equal to $\frac{n(n-1)}{2} - |M| - 1 = \frac{n(n-1)}{2} - \frac{n+1}{2} = \frac{n(n-2)-1}{2}$.

# 4 Hardness of Exact Computation

In this section we provide several hardness results for the DOUBLE UPPER EC and the UPPER r-EC in some graph classes as regular graphs and split graphs.

**Theorem 11.** Let $G = (V, E)$ be an $(r+1)$-regular graph with $r \geq 2$. Then,

$$ uec_r(G) = |E| - \text{eds}(G). \qquad (6) $$

*Proof.* In order to prove this equation, first we will show that if $S \subseteq E$ is a $r$-tec of $G$, then $\bar{S} = E \setminus S$ is an edge dominating set of $G$. Let $(V_1, V_2)$ be the associated partition related to $S$. By the Property 1 we know that $V_2$ is an independent set. Because our graph is $(r+1)$-regular, it is easy to see that $\forall v \in V_1, d_{G_S}(v) = r$ and $\forall u \in V_2, d_{G_S}(u) = r+1$. This observation gives us that the set $\bar{S}$ covers each vertex of $V_1$ (they have degree $r$) and that all the edges in $E$ are incident to a vertex in $V_1$ (because $V_2$ is an independent set). So, $\bar{S}$ is an edge dominating set.
Conversely, let $S$ be a solution of EDS. We will show that there exists a $r$-tec of size $|\bar{S}|$. Because EDS is equivalent to LOWER EM, we consider the edge set $S$ as a maximal matching. Now, let $V' = V \setminus V[S]$. Observe that $V'$ is an independent set in $G$ and each vertex $v \in V'$ has $d_{G_{\bar{S}}}(v) = r+1$. The first holds because if there exists an edge $e$ between two vertices of $V'$ then $S \cup \{e\}$ will be a matching with size greater than $S$, which contradicts the maximality of $S$. The second holds because the edges in $S$ are not incident to vertices of $V'$ by definition, and thus, all the edges in $\bar{S}$ are incident to at least one vertex in $V[S]$. Finally, because $S$ is a matching we have that all the vertices in $V[S]$ have degree $r$ in $G_{\bar{S}}$ so by the property 1, $\bar{S}$ is a $r$-tec. So the Eq. (6) holds. $\square$

**Corollary 12.** UPPER $r$-EC is **NP**-hard in $(r+1)$-regular bipartite graphs.

*Proof.* Using the **NP**-hardness proof of EDS in $r$-regular bipartite graphs given in [15], the results follows from Theorem 11. $\square$

**Corollary 13.** DOUBLE UPPER EC is **NP**-hard in cubic planar graphs.

*Proof.* Using the **NP**-hardness proof of EDS for cubic planar graphs given in [23], the results follows from Theorem 11. $\square$

**Theorem 14.** UPPER $(r+1)$-EC is **NP**-hard in graphs of maximum degree $\Delta+1$ if UPPER $r$-EC is **NP**-hard in graphs of maximum degree $\Delta$, and this holds even for bipartite graphs.

*Proof.* Let $G = (V, E)$ be a bipartite graph of maximum degree $\Delta$, we construct a new graph $G' = (V', E')$ by starting from $r+1$ copies of $G$. Then for each vertex $v \in V$ we add a new vertex $u_v$ in $G'$ and connect it to each one of the $r+1$ copies of the vertex $v$. $\square$

**Remark 15.** Observe that the reverse direction of the proof applies to any $(r+1)$-tec of $G'$. So starting from an $(r+1)$-tec of $G'$ we can construct an $r$-tec of $G$ by checking the $r$-tec of the copies of $G$ in $G'$. Furthermore, if we select the greater one we have the following relation:

$$|r\text{-tec}(G)| \geq \frac{1}{r+1}|(r+1)\text{-tec}(G')| - n$$

**Theorem 16.** DOUBLE UPPER EC is **NP**-hard in split graphs.

*Proof.* The proof is based on a reduction from the 2-tuple dominating set. Let $G = (V, E)$ be an instance of 2-tuple dominating set; we will construct a split graph $G'$: First, for every vertex $v \in V$ we make three copies $v^*$, $v'$, $v''$, and for each vertex $u \in N[v]$ we add the edges $v^*u'$, $v^*u''$. Then we construct a $K_{3,2}$ and in the end we add edges in order to make a complete graph with the vertices of $V^*$ and the only two vertices of one side of $K_{3,2}$. $\square$
# 5 Hardness of Approximation

In the following theorems we provide some inapproximability results for the UPPER EC and the DOUBLE UPPER EC.

**Theorem 17.** It is NP-hard to approximate the solution of UPPER EC to within $\frac{593}{594}$ and $\frac{363}{364}$ in graphs of max degree 4 and 5 respectively.

*Proof.* In order to prove this we will use a reduction from MIN VC. Starting from an r-regular graph $G = (V, E)$ we will construct a new graph $G'$; first we add a $P_2$ to each vertex $v \in V$. Then for each edge $e = vu \in E$ we add a new vertex $v_e$ adjacent to v and u. In the end we remove all the starting edges $E$. Since MIN VC can not be approximated to within a factor $\frac{100}{99}$ (resp. $\frac{53}{52}$) in 3-regular (resp. 4-regular) graphs [11], it deduces the expected results. □

**Theorem 18.** It is NP-hard to approximate the solution of DOUBLE UPPER EC to within $\frac{883}{884}$ in graphs of max degree 6.

*Proof.* In order to get the inapproximability result, we first make a reduction from MIN VC to UPPER EC similar to Theorem 17, then we reduce it to DOUBLE UPPER EC using a reduction proposed in Theorem 14. □

**Theorem 19.** It is NP-hard to approximate the solution of DOUBLE UPPER EC to within $\frac{571}{572}$ in graphs of max degree 9.

*Proof.* Again, we will make a reduction from VERTEX COVER problem. Starting from a 4-regular graph $G = (V, E)$ we construct a new graph by adding a set of new vertices $V_E$ which has one vertex $v_e$ for each edge $e \in E$, and then adding new edges $v_e u$ if the edge $e$ was incident to $u$ in the original graph $G$. Let $G' = (V', E')$ be the new graph. It is easy to see that $|V'| = |V| + |E|$ and $\Delta(G') = 2\Delta(G) = 8$. Furthermore, we can show that from any VC of $G$ we can construct a tec of $G'$ of size $|TEC| = |E| + |V| - |VC|$ and conversely, from any tec of $G'$ we can construct a VC of $G$ of size $|VC| = |E| + |V| - |TEC|$. In order to prove the first direction we will start from a VC of $G$. Let $S$ be the set of all the edges $v_e u$ where $u \in VC$. $S$ is a partial tec of $G$ because it covers only the vertices in $VC \cup V_E$, any vertex of $V_E$ has degree one in $G'_S$ and the vertices of VC are independent in $G'_S$. It is easy to extend $S$ to a tec of $G'$ by adding one edge for every vertex $v \in V \setminus VC$ that is adjacent to a vertex in VC (there exists because $v \in V$ and VC is a vertex cover of $G$). The extended $S$ is a tec due to the fact that the vertices that may have greater degree than one are all in VC, which is independent in $G_S$ and all the vertices are covered. Now we have to observe that this tec contains exactly one edge for each vertex in $V_E$ and one for each vertex in $V \setminus VC$ so the size is exactly

$$|TEC| = |E| + |V| - |VC|.$$

Conversely, we will start from a tec of $G'$ and we will construct a vertex cover of $G$ of the wanted size. First we have to show that for any tec $S$ of $G'$, if there exists $v_e \in V_E$ such that $d_{G'_S}(v_e) = 2$ (it can not be greater because $d_{G'}(v_e) = 2$) then
there exists an other tec S' of G' that has the same size and every vertex $v_e \in V_E$ has degree $d_{G_{S'}}(v_e) = 1$. This is easy to prove by repeating the following:

If there exists $e = uv \in E$ such that $d_{G_{S'}}(v_e) = 2$ then $S' := S' + v_e u - v_e v$.

This process terminates because it reduces the number of such vertices each time by one. Except that we have to show that the last set has the same size and remains a tec. Because $v_e$ has degree two in the starting tec this means that the vertices $u$ and $v$ that were adjacent to it had degree one. In the new set we have degree two in vertex $u$ and degree one in the two neighbors of it, $v_e$ and $v$. So, the new set remains a tec and has the same size because we remove one and add one edge. Now, from $S'$ we will construct a vertex cover of $G$. We claim that the set $U = \{v \in V | N_{G_{S'}}(v) \cap V_E \neq \emptyset\}$ is a vertex cover of $G$ of the desired size. Because for each edge $e \in E$ there exists a vertex $v_e \in V_E$, we have that $U$ is a vertex cover of $G$ (because it dominates the $V_E$). Except that, because we know that in the modified tec every vertex in $V_E$ has degree exactly one and those edges covers only $U$ (by construction) we need to count the edges that covers the remaining vertices. Assume that in our tec the remaining vertices ($V \setminus U$) have degree one and are independent, then the size of our tec is

$$|\text{TEC}| = |E| + |V| - |U| \qquad (7)$$

which gives us the wanted. In order to complete the reduction between VERTEX COVER and UPPER EDGE COVER we need to prove that the last assumption is always true. First observe that if two vertices $v, u \in V \setminus U$ are covered by the same edge in our tec then there exists an edge $uv = e \in E$ and a vertex $v_e \in V_E$. Then in our tec the vertex $v_e$ must be covered by $u$ or $v$ which is a contradiction because non of them are in $U$. Now suppose that there exists vertex $v \in V \setminus U$ such that $d_{G_{S'}}(v) \ge 2$. Because $v \notin U$ we know that there is a $u \in U$ such that $uv \in S'$ and because $u$ must be adjacent to a vertex in $V_E$ in our tec this means that we have two vertices of degree at least two in a tec which is a contradiction.

After that we will do the same reduction between UPPER EC and UPPER 2-EC as in Theorem 14 so we have $uec_2(G'') = 2uec(G') + 2|V'|$ and generally by the remark 15 we have that from any 2-tec, of value $|ec_2|$, of $G''$ we can construct a tec, of value $|ec|$, of $G'$ such that the following equation holds,

$$|ec_2| \le 2|ec| + 2|V'|. \qquad (8)$$

Furthermore we have $m = |E| \le 4|\text{minVC}|$ and $n = |V| \le 2|\text{minVC}|$ (because we started from a 4-regular graph) which implies that from a 2-tec, of value $|ec_2|$, of $G''$ we can construct a vertex cover, $U$, of $G$ that has the following property.

$$|ec_2| \le 4|E| + 4|V| - 2U \qquad (9)$$

The previous equation is easy to prove by the equations 7, 8 and the construction of the graphs. Now we are ready to finish the proof. If we can approximate the solution of UPPER 2-EC within a factor of $1 - a$ then we can have a solution
of value $|ec_2|$ such that $\frac{|ec_2|}{uec_2} \ge 1 - a$. By starting from this solution we can construct a vertex cover $U$ for the graph $G$. Then we have that:

$$ 
\begin{aligned}
|U| - |minVC| & \le \frac{1}{2}(uec_2(G'') - |ec_2|) \le \frac{1}{2}a \text{ uec}_2(G'') \\
& = \frac{1}{2}a (4m + 4n - 2|minVC|)
\end{aligned}
$$

By the relations between $m$, $n$ and $|minVC|$ we have the following:

$$ |U| - |minVC| \le \frac{1}{2}a (4m + 4n - 2|minVC|) \le 11a |minVC| $$

So, we could have a $1+11a$ approximation for vertex cover in 4-regular graphs. Because the vertex cover is not $\frac{53}{52}$ approximable (see [11]) that gives us that $a$ cannot be equal or less than $\frac{1}{11}$ so the solution of DOUBLE UPPER EC is NP-hard to approximate within a factor $\frac{571}{572}$ in graphs of max degree 9. □

**Dedication.** This paper is dedicated to the memory of our dear friend and colleague Jérôme Monnot who sadly passed away while this work was in progress.

## References

1. S. Arumugam, S. T. Hedetniemi, S. M. Hedetniemi, L. Sathikala, and S. Sudha. The covering chain of a graph. *Util. Math.*, 98:183–196, 2015.

2. Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, and Maria Kyropoulou. An improved approximation bound for spanning star forest and color saving. In Rastislav Královic and Damian Niwinski, editors, *Proc. of 34th MFCS*, volume 5734 of LNCS, pages 90–101. Springer, 2009.

3. Sandip Banerjee and Sujoy Bhore. Algorithm and hardness results on liar's dominating set and k-tuple dominating set. In Charles J. Colbourn, Roberto Grossi, and Nadia Pisanti, editors, *Proc. of IWOCA 2019*, volume 11638 of Lecture Notes in Computer Science, pages 48–60. Springer, 2019.

4. Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, and Vangelis Th. Paschos. The many facets of upper domination. *Theor. Comput. Sci.*, 717:2–25, 2018.

5. Alan A. Bertossi. Dominating sets for split and bipartite graphs. *Inf. Process. Lett.*, 19(1):37–40, 1984.

6. Kellogg S. Booth and J. Howard Johnson. Dominating sets in chordal graphs. *SIAM J. Comput.*, 11(1):191–199, 1982.

7. Gerard Jennhwa Chang, Paul Dorbec, Hye Kyung Kim, André Raspaud, Haichao Wang, and Weiliang Zhao. Upper k-tuple domination in graphs. *Discrete Mathematics & Theoretical Computer Science*, 14(2):285–292, 2012.

8. Mustapha Chellali, Odile Favaron, Adriana Hansberg, and Lutz Volkmann. k-domination and k-independence in graphs: A survey. *Graphs and Combinatorics*, 28(1):1–55, 2012.

9. Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, and Gyanit Singh. Improved approximation algorithms for the spanning star forest problem. *Algorithmica*, 65(3):498–516, 2013.
10. Grant A. Cheston, Gerd Fricke, Stephen T. Hedetniemi, and David Pokrass Jacobs. On the computational complexity of upper fractional domination. *Discrete Applied Mathematics*, 27(3):195-207, 1990.

11. Miroslav Chlebík and Janka Chlebíková. Complexity of approximating bounded variants of optimization problems. *Theor. Comput. Sci.*, 354(3):320-338, 2006.

12. Derek G. Corneil and J. M. Keil. A dynamic programming approach to the dominating set problem on k-trees. *SIAM Journal on Algebraic Discrete Methods*, 8(4):535-543, 1987.

13. Peter Damaschke, Haiko Müller, and Dieter Kratsch. Domination in convex and chordal bipartite graphs. *Inf. Process. Lett.*, 36(5):231-236, 1990.

14. Frank K. H. A. Dehne, Michael R. Fellows, Henning Fernau, Elena Prieto-Rodriguez, and Frances A. Rosamond. NONBLOCKER: parameterized algorithms for minimum dominating set. In *Proc. of the 32nd SOFSEM*, volume 3831 of LNCS, pages 237-245. Springer, 2006.

15. Marc Demange, Tinaz Ekim, and Cerasela Tanasescu. Hardness and approximation of minimum maximal matchings. *Int. J. Comput. Math.*, 91(8):1635-1654, 2014.

16. M. Farber. Domination, independent domination and duality in strongly chordal graphs. *Discrete Appl. Math.*, 7:115-130, 1984.

17. Henning Fernau and David F. Manlove. Vertex and edge covers with clustering properties: Complexity and algorithms. *J. Disc. Alg.*, 7:149-167, 2009.

18. J. F. Fink and M. S. Jacobson. Graph theory with applications to algorithms and computer science. chapter n-Domination in Graphs, pages 283-300. John Wiley & Sons, Inc., New York, NY, USA, 1985.

19. Andrei Gagarin and Vadim E. Zverovich. A generalised upper bound for the k-tuple domination number. *Discrete Mathematics*, 308(5-6):880-885, 2008.

20. Michael R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman & Co., New York, NY, USA, 1979.

21. Frank Harary and Teresa W. Haynes. Double domination in graphs. *Ars Comb.*, 55, 2000.

22. Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater. *Fundamentals of domination in graphs*, volume 208 of *Pure and applied mathematics*. Dekker, 1998.

23. Joseph Douglas Horton and Kyriakos Kilakos. Minimum edge dominating sets. *SIAM J. Discrete Math.*, 6(3):375-387, 1993.

24. Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, and Florian Sikora. Weighted upper edge cover: Complexity and approximability. *J. Graph Algorithms Appl.*, 24(2):65-88, 2020.

25. Ralf Klasing and Christian Laforest. Hardness results and approximation algorithms of k-tuple domination in graphs. *Inf. Process. Lett.*, 89(2):75-83, 2004.

26. Chung-Shou Liao and Gerard J. Chang. k-tuple domination in graphs. *Inf. Process. Lett.*, 87(1):45-50, 2003.

27. David F. Manlove. On the algorithmic complexity of twelve covering and independence parameters of graphs. *Disc. Appl. Math.*, 91(1-3):155-175, 1999.

28. C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, and Louxin Zhang. Approximating the spanning star forest problem and its application to genomic sequence alignment. *SIAM J. Comput.*, 38(3):946-962, 2008.

29. Alexander Schrijver. *Combinatorial Optimization: Polyhedra and Efficiency*. Springer-Verlag, 2003.

30. P. J. Slater. Enclaveless sets and MK-systems. *J. Res. Nat. Bur. Stand.*, 82(3):197-202, 1977.