Faisal N Abu-Khzam
email: faisal.abukhzam@lau.edu.lb

Cristina Bazgan
email: bazgan@lamsade.dauphine.fr

Morgan Chopin
email: morgan.chopin@uni-ulm.de

Henning Fernau
email: fernau@uni-trier.de

Approximation Algorithms Inspired by Kernelization Methods

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.

Introduction

In this paper, for the purpose of illustrating our method, we will mainly deal with maximization problems that are obtained from domination-type graph problems. We first describe these problems, using standard graph-theoretic terminology.

Let G = (V, E) be an undirected graph and D ⊆ V .

1. D is called a dominating set if, for all x ∈ V \ D, there is a y ∈ D ∩ N (x).

V \ D is known as an enclaveless set [START_REF] Slater | Enclaveless sets and MK-systems[END_REF] or as a nonblocker set [START_REF] Dehne | Nonblocker: parameterized algorithmics for minimum dominating set[END_REF]. 2. D is called a total dominating set if, for all x ∈ V , there is a y ∈ D ∩ N (x).

V \ D has been introduced as a harmless set or robust set (with unaminity thresholds) in [START_REF] Bazgan | The robust set problem: Parameterized complexity and approximation[END_REF]. 3. If D can be partitioned as D = D 1 ∪ D 2 such that, for all x ∈ V \ D, there is a y ∈ D 2 ∩ N (x), then (D 2 , D 1 ) defines a Roman domination function f D1,D2 : V → {0, 1, 2} such that f D1,D2 (V ) = 2|D 2 |+|D 1 |. According to [START_REF] Bermudo | The differential and the Roman domination number of a graph[END_REF],

|V | -f D1,D2 (V ) is also known as the differential of a graph (as introduced in [START_REF] Mashburn | Differentials in graphs[END_REF]) if f D1,D2 (V ) is smallest possible. 4. If for all x ∈ V \D, there are k elements in D∩N (x), then D is a k-dominating set, see [START_REF] Caro | A note on the k-domination number of a graph[END_REF][START_REF] Cockayne | An upper bound for the k-domination number of a graph[END_REF][START_REF] Fink | n-domination in graphs[END_REF]. We will call V \ D a k-nonblocker set.

The maximization problems derived from these four definitions are: Nonblocker, Harmless Set, Differential, and k-Nonblocker. Although these problems are all better known from the minimization perspective, there is a good reason to study them in this complementary way: All of these minimization problems do not possess constant-factor approximations under reasonable complexity assumptions (the reduction shown in [START_REF] Chlebík | Approximation hardness of dominating set problems in bounded degree graphs[END_REF] for (Total) Dominating Set starts from Set Cover), while the complementary problems can be treated in this favorable way. For Roman Domination, observe that the reduction shown in [START_REF] Fernau | Roman Domination: a parameterized perspective[END_REF] works from Set Cover, so that again (basically) the same lower bounds follow. This move is related to differential approximation [START_REF] Ausiello | Completeness in differential approximation classes[END_REF]. Notice that this comes along with similar properties from the perspective of Parameterized Complexity: While natural parameterizations of the minimizations lead to W [START_REF] Athanassopoulos | An improved approximation bound for spanning star forest and color saving[END_REF]-hard problems [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Fernau | Roman Domination: a parameterized perspective[END_REF], the natural parameterizations of the maximization counterparts are fixed-parameter tractable. However, as this is more customary as a combinatorial entity, let us refer (as usual) by γ(G) to the size of the smallest dominating set of G, by γ t (G) to the size of the smallest total dominating set, by γ R (G) to the Roman domination number of G, i.e., the smallest value of a Roman domination function of G, and by γ k (G) to the size of the smallest k-dominating set of G. Some graph-theoretic notations. Let G = (V, E) be a simple undirected graph. We denote by N (x) the set of neighbors of vertex x; the cardinality of N (x) is the degree of x. A vertex of degree zero is known as an isolated vertex, and a vertex of degree one as a leaf. The number of vertices of a graph is called its order. Given U ⊆ V , G[U ] denotes the subgraph induced by U . A repetition-free sequence x 1 , . . . , x k of vertices is a path in G (of length k -1) if x i x i+1 ∈ E for i = 1, . . . , k -1. A chain is an induced path whose interior vertices are of degree two in G. The diameter of G is the greatest length of a shortest path in G.

Main Results. We introduce a notion of approximation-preserving reductions analogous to parameter-preserving reductions known in Parameterized Complexity in order to obtain new approximation algorithms. We introduce a general methodology to obtain constant-factor approximations for various problems. For instance, along with an algorithmic version of the upper bound obtained in [START_REF] Lam | On the total domination number of graphs[END_REF] on the size of a total dominating set, we present a factor-two approximation algorithm for Harmless Set, beating the previously known factor of three [START_REF] Bazgan | The robust set problem: Parameterized complexity and approximation[END_REF]. Moreover, we are deriving a factor- 11 3 approximation algorithm for Differential, which was set up as an open problem in [START_REF] Bermudo | Computing the differential of a graph: hardness, approximability and exact algorithms[END_REF], where this approximability question could be only settled for bounded-degree graphs; our approach also improves on the factor-4 approximation exhibited in [START_REF] Bermudo | Combinatorics for smaller kernels: The differential of a graph[END_REF]. Finally, we present constant-factor approximation algorithms for k-Nonblocker.

Organization of the paper. Section 2 explains the use of reduction rules within maximization problems. It also exhibits the general method. Section 3 shows how to employ our general method to one specific problem in a non-trivial way. Sec-tions 4 and 5 show that the same method can be also applied to other problems. We conclude with discussing further directions of research.

All proofs and some more details that are omitted due to space restrictions can be found in the long version of this paper [1].

Approximation preserving reductions for maximization problems

A maximization problem P can be specified by a triple (I P , SOL P , m P ), where 1. I P is the set of input instances of P; 2. SOL P is a function that associates to x ∈ I P the set SOL P (x) of feasible solutions of x; 3. m P provides on (x, y), where x ∈ I P and y ∈ SOL P (x), a positive integer which is the value of the solution y.

An optimum solution y * to x satisfies: (i) y * ∈ SOL P (x), and (ii) m P (y * ) = max{m P (y) | y ∈ SOL P (x)}. The value m P (y * ) is also referred to as m * P (x) for brevity. The subscript P will be dropped when no ambiguity exists.

Given a maximization problem P, a factor-α approximation, α ≥ 1, associates to each x ∈ I P some y ∈ SOL P (x) such that α • m P (x, y) ≥ m * P (x). A solution y ∈ SOL P (x) satisfying α • m P (x, y) ≥ m * P (x) is also called an α-approximate solution for x.

We are now going to present a first key notion for this paper.

Definition 1. An α-preserving reduction, with α ≥ 1, is a pair of mappings inst P : I P → I P and sol P which, given y ∈ SOL P (inst P (x)), produces some y ∈ SOL P (x) such that there are constants a, b ≥ 0 satisfying a ≤ α • b and the following inequalities:

1. m * P (inst P (x)) + a ≥ m * P (x), 2. for each y ∈ SOL P (inst P (x)), the corresponding solution y = sol P (y ) satisfies: m P (inst P (x), y ) + b ≤ m P (x, y).

When referring to this definition, we mostly explicitly specify the constants a and b for ease of verification. An important trivial example is given by a pair of identity mappings that are α-preserving for any α ≥ 1. Notice that a similar notion has been introduced in the context of minimization problems in [START_REF] Brankovic | Parameterized approximation algorithms for Hitting Set[END_REF][START_REF] Brankovic | A novel parameterised approximation algorithm for minimum vertex cover[END_REF][START_REF] Fomin | Planar F -deletion: Approximation, kernelization and optimal FPT algorithms[END_REF].

Theorem 1. Let P = (I P , SOL P , m P ) be some maximization problem. If the pair (inst P , sol P ) describes an α-preserving reduction and if, given some instance x, y ∈ SOL P (inst P (x)) is an α-approximate solution for inst P (x), then y = sol P (y ) is an α-approximate solution for x.

Proof. We have to prove that α • m P (x, y) ≥ m * P (x). Now, m * P (x) m P (x, y) ≤ m * P (inst P (x)) + a m P (inst P (x), y ) + b ≤ αm P (inst P (x), y ) + αb m P (inst P (x), y ) + b = α as required.

This shows that an α-preserving reduction leads to a special AP-reduction as defined in [START_REF] Ausiello | Complexity and Approximation[END_REF]. But there, these reductions were mainly used to prove hardness results, as it is also the case of [START_REF] Fomin | Planar F -deletion: Approximation, kernelization and optimal FPT algorithms[END_REF] that we already mentioned. However, we use this notion to obtain approximation algorithms.

The notion of an α-preserving reduction was coined following the successful example of kernelization reductions known from Parameterized Complexity [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF]. One of the nice features of those is that they are usually compiled from simpler rules that are often based on some applicability conditions. In the following, we describe that this also works out for approximation. We need two further notions to make this precise.

We call an α-preserving reduction (inst P , sol P ) strict if | inst P (x)| < |x| for all x ∈ I P , and it is called polynomial-time computable if the two mappings comprising the reduction can be computed in polynomial time.

Lemma 1. If (inst P , sol P ) and (inst P , sol P ) are two α-preserving reductions, then the composition (i, s) := (inst P • inst P , sol P • sol P ) is also an αpreserving reduction. If both (inst P , sol P ) and (inst P , sol P ) are strict (polytime computable, resp.), then the composition (i, s) is strict (poly-time computable, resp.).

Reductions are often described in some conditional form: if condition then do action Our previous considerations apply also for this type of conditioned reductions, apart from the fact that an instance may not change, assuming that the reduction was not applicable, which means that the condition was not true for that instance. Further discussions can be found in the long version of the paper [1].

The general strategy that we follow can be sketched as follows:

1. Apply (strict, poly-time computable) α-preserving reduction rules as long as possible. 2. Possibly modify the resulting graph so that it meets some requirements from known combinatorial results on the graph parameter of interest. 3. Compute some solution for the modified graph that satisfies the mentioned combinatorial bounds. 4. Construct from this solution a good approximate solution for the original instance.

In order to illustrate the use of this strategy, let us elaborate on Nonblocker, matching a result from [START_REF] Nguyen | Approximating the spanning star forest problem and its application to genomic sequence alignment[END_REF]; the current record is given in [START_REF] Athanassopoulos | An improved approximation bound for spanning star forest and color saving[END_REF]. This goes along the lines of the kernelization result by Dehne et al. [START_REF] Dehne | Nonblocker: parameterized algorithmics for minimum dominating set[END_REF], but kernelization needs no constructive proof of the combinatorial backbone result; the non-constructive proof of [START_REF] Mccuaig | Domination in graphs of minimum degree two[END_REF] 5 3 -approximate. 7. As the merging and deletion reductions are α-preserving for each α ≥ 1, we can safely undo them and hence obtain a 5 3 -approximate solution for the original graph instance.

D G = V G ∩ D H is a dominating set for G with |D G | ≤ 2 5 n G . Trivially, N G = V G \ D G is a nonblocker solution for G that is

Harmless Set

We are now turning towards Harmless Set as the most elaborate example of our methodology. First, we are going to present the combinatorial backbone of our result. Let S 2 (G) be the set all vertices of degree two within G.

Theorem 2. (Lam and Wei [START_REF] Lam | On the total domination number of graphs[END_REF]) Let G be a graph of order n G and of minimum degree at least two such that

G[S 2 (G)] decomposes into K 1 -and K 2 -components. Then, γ t (G) ≤ n G /2.
The proof of this theorem is non-constructive, as it uses tools from extremal combinatorics. In [1], we show how to obtain a polynomial-time algorithm that actually computes a total dominating set (TDS) D with |D| ≤ n G /2 under the assumptions of Theorem 2. Our approximation algorithm for Harmless Set is based on obtaining a (small enough) TDS in a graph H obtained from the input G after a number of modifications (mainly vertex deletions). In the reduction from G to H, we distinguish between the number of deleted vertices d (to get from G to H) and the number of vertices a that are added to convert the TDS D H to D G . Theorem 3. Let G be a graph of order n G and let H be a graph of order n H obtained from G by deleting d vertices and possibly adding some edges. Let D G and D H be TDS solutions of G and Hsuch that a

= |D G | -|D H | ≤ d. If |D H | ≤ c•n H and d ≤ γ t (G), then V (G)\D G is a harmless set of G whose size n G -|D G | is within a factor of (1 -c) -1 from optimum. Proof. As n H = n G -d, |D G | = |D H | + a ≤ c(n G -d) + a = cn G + (a -cd) ≤ cn G + d -cd = cn G + (1 -c)d ≤ cn G + (1 -c)γ t (G). Hence, n G -|D G | ≥ n G -cn G -(1 -c)γ t (G) = (1 -c)(n G -γ t (G))
. This immediately yields an approximation factor of (1 -c) -1 .

In the following, we will present reduction rules that produce a graph G with the property (*) that each vertex of degree bigger than one has at most one leaf neighbor. The surgery that produces a graph H from G as indicated in Theorem 3 includes removing all d leaves and adding edges to ensure that H has minimum degree of two and satisfies that each component of H[S 2 (H)] has diameter at most one. Notice that all leaf neighbors in G belong to some optimum TDS of G without loss of generality. Due to (*), γ t (G) ≥ d as required. Moreover, given some TDS solution D H for H, we can produce a valid TDS solution D G for G by adding all d leaf neighbors to D H . Notice that Theorem 3 leads to a factor-2 approximation algorithm for Harmless Set based on a polynomial-time, constructive version of Theorem 2. Now, we list α-preserving reductions for Harmless Set. All missing correctness proofs can be found in the long version of this paper [1]. We start with two very simple rules.

Isolate Reduction. If there is some isolated vertex, produce the instance ({x}, ∅) that has trivially no solution.

Leaf Reduction. If there are two leaf vertices u, v with common neighbor w, then delete u. (It would go into the harmless set.) Observation 4 The Leaf Reduction is α-preserving for any α ≥ 1.

Hence from now on, no vertex can have two leaf neighbors. We shall use the term chain to denote a path whose interior vertices are of degree two in G. A chain with one leaf endpoint is a pendant chain. A floating chain is a chain with two leaves. A support vertex is a non-pendant endpoint of a pendant chain. Support vertices may have more than one pendant chain. We shall reduce the length of pendant chains to at most two, based on the following reduction rules.

Floating Chain Reduction. Delete all floating chains.

Clearly, a maximum harmless set (and a minimum TDS) can be computed in linear time on such trivial connected components. Hence, we can verify the definition with suitably chosen values for a = b, which proves: Observation 5 The Floating Chain Reduction is α-preserving for any α ≥ 1.

Long Chain Reduction. Assume that G is a graph that contains a path x -u -v -w -y, where u, v, w are three consecutive vertices of degree two, where |N (y)| ≥ 2. Then, construct the graph G by merging x and y and deleting u, v, w. Theorem 6. The Long Chain Reduction is α-preserving for any α ≥ 1.

Proof. Let G be the original graph and G the graph obtained from G by deleting the path u, v, w and merging x and y as described by the rule. We show that a = b = 2 works out in our case by considering several cases. (a) Let C be a maximum harmless set (HS) for G. The special case when N (x) = {u} is easy to verify. In the following discussion, we can hence assume that x has at least two neighbors. We now consider cases whether or not x ∈ C or y ∈ C. Similarly, one sees the correctness of the following rule.

Cycle Chain Reduction. If G is a graph that contains a cycle x-u-v -w-x, where u, v, w are three consecutive vertices of degree two, then construct G by deleting u.

Finally, we deal with support vertices with multiple pendant chains. Assuming the Long Chain Reduction has been applied, any pendant chain is of length two or less. Accordingly, a support vertex where two of more pendant chains meet does belong to some optimum solution. The following rule makes this idea more precise.

Pendant Chain Reduction. Assume that G = (V, E) is a graph that contains two pendant chains with common endpoint v of which at least one path is of length two. Then, construct the graph G = (V , E ) by deleting one of the two pendant chains, keeping one which is of length two.

Theorem 7. The Pendant Chain Reduction is α-preserving for any α ≥ 1.

We are now ready to apply Theorem 3. Assume the graph G = (V, E) is reduced according to the reduction rules described so far. Hence, G satisfies: (a) G contains no chain of three vertices of degree two. (b) By the Leaf Reduction rule, any vertex has at most one leaf neighbor. Let G be a graph isomorphic to G so that each vertex v of G corresponds to a vertex v of G , under the assumed isomorphism f : V (G) -→ V (G ). We construct a graph H obtained from the disjoint union of G and G simply by adding edges between each leaf neighbor vertex v of G and v = f (v) ∈ V (G ). Then, we remove all leaves.

Due to the application of Pendant Chain Reduction to G (and G ), the addition of edges between corresponding leaf neighbors in G and G does not introduce induced cycles with more than two consecutive degree-two vertices.

To the resulting graph H, apply Long Chain Reduction as long as possible. Notice that an application of this rule does never decrease degrees, adds two vertices to the solution and removes four vertices of the graph.

This results in a graph H of order n H with minimum degree at least two containing no chain of three vertices of degree two. Hence, we can apply the (algorithmic) version of Theorem 2 that returns a TDS D H for H with 2|D H | ≤ n H . Undoing the c Long Chain Reductions that we applied, we obtain a TDS H) by an edge xy not belonging to G, then we must add another neighbor z (in G) of x to D G . However, as (obviously) the vertex y belonged to D H and was dominated by a neighbor (in G) in D H , we add (in total) two vertices x, z for the two support vertices x, y. Seen from the other side, this covers the case of a support vertex that already belonged to D H but was not dominated via the edge that we introduced.

D H for H with 2|D H | = 2(|D H | + 2c) ≤ n H + 4c = n H . By symmetry, we can assume that |D H ∩ V (G)| ≤ |D H ∩ V (G )|. Now,
Altogether, we see that we delete all leaves and introduce at most that many vertices into D G (in comparison to D H ∩ V (G)). By Theorem 3 and since all reduction rules take polynomial time, we obtain: Theorem 8. Harmless Set is factor-2 polynomial-time approximable.

The differential of a graph

Let us start with an alternative presentation of this notion. Let G = (V, E) be a graph. For

D 0 ⊆ V , let ∂(D 0 ) := x∈D0 N (x) \ D 0 -|D 0 |. ∂(D 0
) is called the differential of the set D 0 , and our aim is to find a vertex set that maximizes this quantity. This maximum quantity is known as the differential of G, written ∂(G). The following combinatorial results are known: It is not hard to turn the first combinatorial result into a kernelization result, yielding a kernel bound of 5k, where k is the natural parameterization of the Differential. In [START_REF] Bermudo | Combinatorics for smaller kernels: The differential of a graph[END_REF], this result was improved to a kernel whose order is bounded by 4k. This way, we can also get a factor-4 approximation. However, Theorem 9 suggests a possible improvement to a factor of 11 3 by our framework. First, we have to show (see [1] more details) that the reduction rules presented in [START_REF] Bermudo | Combinatorics for smaller kernels: The differential of a graph[END_REF] as kernelization rules can be also interpreted as α-preserving rules. We use some non-standard terminology. A hair is a sequence of two vertices uv, where u is a leaf and v has degree two. Then, u is also called a hair leaf. Lemma 2. [START_REF] Bermudo | Combinatorics for smaller kernels: The differential of a graph[END_REF] Let G = (V, E) be a graph where none of the Differential reduction rules listed in [1,[START_REF] Bermudo | Combinatorics for smaller kernels: The differential of a graph[END_REF] applies. Then, G has the following properties:

(1) To each vertex, at most one leaf or one hair is attached, but not both together.

(2) If we remove all leaves and all hairs from G, then the remaining graph G = ( Ṽ , Ẽ), henceforth called nucleus, has minimum degree of at least two.

(3) If a hair is attached to a vertex u in the nucleus, then no hair is attached to any neighbor of u within the nucleus.

We compute a sufficiently big solution for the nucleus and then use:

= |D G,1 | -|D H,1 | ≤ d. If |D H,1 | + 2|D H,2 | ≤ c • n H and d ≤ γ R (G), then ∂(V (G) \ D G ) = n G -2|D G,2 | -|D G,1 | is within a factor of (1 -c) -1 from optimum.
We can turn the (non-constructive) combinatorial reasoning of [START_REF] Bermudo | Lower bounds on the differential of a graph[END_REF] into a polynomial-time algorithm (see [1]), which allows us to conclude: Theorem 11. Differential is factor- 11 3 polynomial-time approximable.

Multiple Nonblocker sets

We shall assume k > 1 in this section and, as usual, we consider a combinatorial upper bound on the size of some feasible solution of the minimization problem.

Theorem 12 ([16]). Let G be a graph of order n G and a minimum degree at least k. Then γ k (G) ≤ k k+1 n G . The known non-constructive proof can be turned into a polynomial-time algorithm (see [

= |D G | -|D H | = d -k. If |D H | ≤ c • n H for some c < 1 and d ≤ γ k (G), then V (G) \ D G is a k-nonblocker of G whose size n G -|D G | is within a factor of (1 -c) -1 from optimum.
This result is understood modulo the additive constant k(2c -1) < k. Given a graph G as input, we construct a graph G obtained from G by adding a complete bipartite graph K k,k with (new) vertices u 1 , . . . , u k , v 1 , . . . , v k . This transformation is an L-reduction (as defined in [START_REF] Ausiello | Complexity and Approximation[END_REF]) and thus the approximation ratio is preserved. Now, we present reduction rules that when applied to G produce a graph H with minimum degree at least k. Our reduction rules mainly deal with vertices of degree k -1 or less. We refer to such vertices as low-degree vertices. Each such vertex must be in any k-dominating set.

Low-Degree Vertex Deletion. If a low-degree vertex v has only low-degree neighbors, then delete v. If there is a vertex u with at least k + 1 low-degree neighbors, then delete the edge between u and one low-degree neighbor of u.

Observation 15 Low-Degree Vertex Deletion is α-preserving for any α ≥ 1.

Low-Degree Merging. Consider a graph that has been subject to the Low-Degree Vertex Deletion rule. For every vertex v of degree at least k, having q low-degree neighbors w 1 , . . . , w q , with q ≤ k, connect v to v 1 , . . . , v q (from the K k,k that was added as described above). Finally, delete all low-degree vertices.

Observation 16 Low-Degree Merging is α-preserving for any α ≥ 1.

The reductions above take polynomial time, so that Theorem 14 allows us to conclude: Theorem 17. k-Nonblocker is factor-(k + 1) polynomial-time approximable (modulo an additive constant less than k).

Conclusions

We presented a framework for obtaining approximations for maximization problems, inspired by similar reasonings for obtaining kernelization results. We see five directions from this approach:

-Paraphrasing [START_REF] Estivill-Castro | FPT is P-time extremal structure I[END_REF], we might say that not only FPT, but also polynomial-time maximization is P-time extremal structure. This should inspire mathematicians working in combinatorics to work out useful bounds on different graph parameters. We started on domination-type parameters, and this might be a first venue of continuation, for example, along the lines sketched in [START_REF] Borowiecki | Generalized independence and domination in graphs[END_REF][START_REF] Kämmerling | Roman k-domination in graphs[END_REF]. -Conversely, approximation algorithms that stay within the combinatorial grounds of their problem tend to reveal (combinatorial) insights into the problem that might get lost when moving for instance into the area of Mathematical Programming. -The notion of α-preserving reduction is similar to the local ratio techniques [START_REF] Bar-Yehuda | Local ratio: a unified framework for approximation algorithms[END_REF] that allowed to re-interpret many approximation algorithms (for minimization problems) in a purely combinatorial fashion. We see hope for similar developments using α-preserving reduction for maximization problems. -The fact that α-preserving reductions are inspired by FPT techniques should allow to adapt these notions for parameterized approximation algorithms. -Reductions are often close to practical heuristics and hence allow for fast implementations.

( a1 )

 a1 Assume that x ∈ C and y ∈ C. Hence, u, w are not dominated neither by x nor by y. Since C is maximum, we can assume |C ∩ {u, v, w}| = 1, as min{|N (x)|, |N (y)|} ≥ 2; hence, if all of u, v and w are in V \ C, then we can replace w by another neighbor of y and obtain another optimum solution. Then, C = C \ {x, u, v, w} is a HS of G , with |C | = |C| -2. (a2) Assume that x / ∈ C and y / ∈ C. First, let us discuss the possibility that u / ∈ C and w / ∈ C. As C is maximum, the purpose of this is to dominate (i) v and (ii) x and y. To accomplish (i), either u / ∈ C or w / ∈ C would suffice. However, as C is maximum, condition (ii) means that N (x) \ C = {u} and that N (y) \ C = {w}. By our assumptions, min{|N (x)|, |N (y)|} ≥ 2. Hence, there is a vertex z ∈ N (y), z = w. Now, C = (C \ {z}) ∪ {w} is also a maximum HS satisfying {v, w} ⊆ C. From now on, we assume that |C ∩ {u, v, w}| = 2 and that |((N (x) ∪ N (y)) \ ({u, w} ∪ C)| ≥ 1. Hence, C = C \ {u, v, w} is a HS of G with |C | = |C| -2. (a3) Assume now that x ∈ C and y / ∈ C. (Clearly, the case that x / ∈ C andy ∈ C is symmetric.) As u is not dominated by x, either (i) {u, v} ⊆ V \ C or (ii) {v, w} ⊆ V \ C. In case (i),x is dominated by u, but y must (still) be dominated by some vertex from N (y) \ {w}. In case (ii), symmmetrically y is dominated by w, but x must be dominated by some vertex from N (x) \ {u}. In both cases, C = (C \ {x}) ∪ {v} is another maximum harmless set of G. This leads us back to the previous item (i.e., |C | = |C| -2.) Summarizing, we have shown that from C we can construct a harmless setC for G with |C | = |C| -2. (b)Conversely, assume C is some harmless set for G . We distinguish two cases: (b1) Assume that y ∈ C . Then, y is dominated by some z in its neighborhood (in G ). We consider two cases according to the situation in G. (i) If z ∈ N (x), then C = C ∪ {x, u} is a HS in G. (ii) If z ∈ N (y), then C = C ∪ {x, w} is a HS in G. In both cases, |C| = |C | + 2. (b2) If y / ∈ C, then again y is dominated by some z in its neighborhood (in G ). We perform the same case distinction as in the previous case: (i) If z ∈ N (x), then C = C ∪ {u, v} is a HS in G. (ii) If z ∈ N (y), then C = C ∪ {v, w} is a HS in G. In both cases, |C| = |C | + 2. (c) The reasoning from (b) shows that, if C is an optimum solution for G, then C as obtained in part (a) of this proof is an optimum solution for G .

  we add all support vertices to D H ∩ V (G) and further vertices to obtain D G by the following rules: -If a support vertex already belongs to D H , then it could have been dominated via the edge that we introduced. As this interconnects to another support vertex, both already belonged to D H . We arbitrarily select two neighbors (in G) of these support vertices and put them into D G . Hence, the mentioned support vertices and the attached leaves are totally dominated. -If a support vertex x did not already belong to D H , two cases arise: (a) If it was dominated (in H) via an edge already belonging to G, then we do nothing on top of what we said. (b) If the support vertex x was dominated (in

Theorem 9 .

 9 [START_REF] Bermudo | Lower bounds on the differential of a graph[END_REF] Let G be a connected graph of order n.(a) If n ≥ 3, then ∂(G) ≥ n/5. (b) If G has minimum degree at least two, then ∂(G) ≥ 3n11 , apart from five exceptional graphs, none of them having more than seven vertices.

Theorem 10 .

 10 Let G be a graph of order n G and let H be a graph of order n H obtained from G by deleting d vertices. Let D G = D G,1 ∪ D G,2 and D H = D H,1 ∪ D H,2 be Roman DS solutions of G and H, with D H,2 = D G,2 and a

  is hence sufficient. 1. Delete all isolates. (If the resulting graph is of minimum degree at least two, we are ready to directly apply the algorithm of Nguyen et al. [27].) 2. Merge all leaf neighbors into a single vertex. 3. Delete all leaves but one, which is x. This yields the graph G of order n G . 4. Create a copy G of the graph G; call the vertices in the new graph by priming the names of vertices of G. Let H be the graph union of G and G plus the edge xx . H is of minimum degree at least two by construction. 5. Take the algorithm of Nguyen et al. [27] to obtain a dominating set D H of H satisfying |D H | ≤ 2 5 n H . Should the solution D H contain x or x , it is not hard to modify it to contain the leaf neighbors y or y , instead. 6. Hence,

  1]) computing a k-dominating set D with |D| ≤ k k+1 n G . Theorem 13. For a given graph G of order n G and minimum degree at least k, one can compute a k-dominating set D with |D| ≤ k k+1 n G in polynomial time. Our approximation algorithm is based on obtaining a k-dominating set in a graph H obtained from the input G after adding the complete bipartite graph K k,k and after a number of modifications. Theorem 14. Let G be a graph of order n G and let H be a graph of order n H obtained from G by deleting d vertices and adding 2k new vertices, d > k. Let D G and D H be k-dominating set solutions of G and H such that a

Acknowledgements. We are grateful for the support by the bilateral research cooperation CEDRE between France and Lebanon (grant number 30885TM).