New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set

Abstract

An edge dominating set in a graph G = (V, E) is a subset S of edges such that each edge in E − S is adjacent to at least one edge in S. The edge dominating set problem, to find an edge dominating set of minimum size, is a basic and important NP-hard problem that has been extensively studied in approximation algorithms and parameterized complexity. In this paper, we present improved hardness results and parameterized approximation algorithms for edge dominating set. More precisely, we first show that it is NP-hard to approximate edge dominatingset in polynomial time within a factor better than 1.18. Next, we give a parameterized approximation schema (with respect to the standard parameter) for the problem and, finally, we develop an O ^∗(1.821^τ)-time exact algorithm where τ is the size of a minimum vertex cover of G.

1 Introduction

As one of the basic problems in Garey and Johnson’s work on NP-completeness [15], edge dominating set has received high attention in history. It is NP-hard even in planar or bipartite graphs of maximum degree 3 [24]. Due to its theoretical and practical interests, many algorithms have been developed in order to tackle it. There is a simple 2-approximation algorithm for edge dominating set in unweighted graphs. It is not hard to verify that any maximum matching in the graph is an edge dominating set of size at most double of the minimum size. Carr et al. [6] proved a $(2+\frac {1}{10})$-approximation algorithm for weighted edge dominating set (the generalization of edge dominating set where weights are assigned to the edges of the input graph and the objective becomes to determine a minimum total-weight edge dominating set), the ratio of which was later improved to 2 by Fujito and Nagamochi [14]. Improved results have also been obtained in sparse graphs [5] and in dense graphs [19]. However, providing an approximation algorithm with ratio (strictly) smaller than 2, or proving that such algorithm does not exist (under some likely complexity hypothesis) still remains as an open problem. Chlebik and Chlebikova [8] proved that it is NP-hard to approximate it within any factor better than $\frac {7}{6}$. Assuming the unique game conjecture (UGC), [19] showed some inapproximability results on dense instances, a corollary of which is that for every ε > 0edge dominating set is inapproximable within ratio 3/2 − ε (under UGC).

In terms of parameterized complexity, edge dominating set, with parameter k being the size of the solution, is fixed-parameter tractable (FPT). Fernau [12] gave an O ^∗(2.6181^k)-time algorithm that has been subsequently improved by Fomin et al. [13] downto O ^∗(2.4181^k) and by Binkele-Raible and Fernau [1] downto O ^∗(2.3819^k). Currently, the best result is the O ^∗(2.3147^k)-time algorithm by Xiao et al. [21]. When the graph is restricted to be of maximum degree 3, the result can be further improved to O ^∗(2.1479^k) [22]. There is also a long list of contributions to exact algorithms for edge dominating set, such as the O ^∗(1.4423^|V|)-time algorithm by Raman et al. [18], the O ^∗(1.4082^|V|)-time algorithm by Fomin et al. [13], the O ^∗(1.3226^|V|)-time algorithm by Rooij and Bodlaender [20], and finally the O ^∗(1.3160^|V|)-time algorithm by Xiao and Nagamochi [23].

In this paper, we study parameterized approximation for edge dominating set. A parameterized approximation algorithm is a technique combining parameterization and approximation for getting approximation algorithms with fixed-parameter running time. In this way, we may be able to achieve approximation ratios unachievable (or yet unachieved) in polynomial time via fixed-parameter running times that are smaller than the running times of exact algorithms. We may also be able to use this technique to handle W[1]-hard problems which unlikely have fixed-parameter tractable algorithms. The interested reader can be referred to [4, 10, 17] for more about this issue. Let the parameter k be the size of the solution to our problem. In the FPT framework, we want to design algorithms with running time f(k)|I|^O(1) that decide whether there is a solution of size at most k or not, where f is a computable function. In approximation algorithms, we are interested in designing polynomial-time algorithms to find a solution of size g(k), where g is a computable function. In parameterized approximation, we wish to design algorithms with running time f(k)|I|^O(1) that either find an approximate solution of size g(k) or report that there is no solution of size k. Clearly, any fixed-parameter tractable problem allows parameterized approximation algorithms for any computable function g. However, this may not hold for W[1]-hard problems. For example, the dominating set problem (find a set S of k vertices in graph G = (E, V) such that each vertex in V − S is adjacent to at least one vertex in S) does not allow parameterized approximation algorithms for g(k) of the form k + c with fixed constant c [10]. For edge dominating set, we are interested in designing parameterized approximation algorithms, which produce edge dominating sets of size at most (1+ε)k (or assert that there is no solution of size k) in f(k, ε)|I|^O(1) time for some computable function f. Of course, the goal is to find such an algorithm for a function f which is smaller than the O ^∗(2.3147^k)-time (exact) FPT algorithm by Xiao et al. [21]. This issue has already been considered for other FPT problems, in particular for the min vertex cover problem. In[2, 3] several parameterized approximation algorithms running faster than (exact) FPT algorithms and achieving ratios better than the ratio 2 (achievable in polynomial time) are given. Note that [3] asks as open question if similar results can be achieved for edge dominating set.

The remaining parts of this paper are organized as follows. In Section 2, we give an improved hardness result for edge dominating set by showing that it is not $5\sqrt {5}-10+\varepsilon < 1.18$ approximable in polynomial time unless P=NP. In Sections 3 and 4 we tackle parameterized approximation algorithms, answering positively to the open question in [3]. More precisely, in Section 3, we first give a simple algorithm to present the basic ideas, and then improve this algorithm in Section 4. We conclude the article in Section 5 by devising a parameterized algorithm for edge dominating set where the parameter is the vertex cover number of the graph.

2 An Improved Polynomial-Time Lower Bound

In this section, we give some new hardness results for edge dominating set, which are based on a reduction preserving approximation from the famous min vertex cover problem (find a minimum subset S of vertices in a graph such that each edge has at least one endpoint in S) to edge dominating set.

Before, recall some existing results between min vertex cover and edge dominating set. The first two are rather folklore: there exist two simple approximation preserving reductions between min vertex cover and edge dominating set transforming a polynomial-time ρ-approximation algorithm for one of them into a polynomial-time 2ρ-approximation algorithm for the other one. Let G = (V, E) be a simple graph and let M ^∗ ⊆ E and C ^∗ ⊆ V be a minimum edge dominating set and a minimum vertex cover of G, respectively. We will use τ = |C ^∗| to denote the size of a minimum vertex cover of G. Since, it is well known that M ^∗ can be supposed to be a maximal matching, we get τ = |C ^∗| ⩾ |M ^∗|. Also V(M ^∗), the set of endpoints of M ^∗, forms a vertex cover of G and then 2 |M ^∗| ⩾ τ. Thus:

$$ \tau\geqslant |M^{*}|\geqslant \frac{\tau}{2}. $$

(1)

Now, from any ρ-approximation algorithm for min vertex cover given by V′, we can polynomially find an edge dominating set E′ by taking at most one arbitrary edge incident to each vertex of V′. Thus, using (1) we get: |E′| ⩽ |V′| ⩽ ρ × τ ⩽ 2ρ|M ^∗|. Conversely, from any ρ-approximation algorithm for edge dominating set given by M′, we can construct a vertex cover V′ = V(M′) of G by taking the endpoints of M′. Hence, using (1) we deduce: |V′| = 2|M′| ⩽ 2ρ|M ^∗| ⩽ 2ρ × τ.

In Theorem 1 just below, we improve the expansion 2ρ of the reduction to 2ρ − 1. Dealing with weighted versions of these two problems, it is proved in [6] that weighted min vertex cover can be approximated as well as weighted edge dominating set.

Theorem 1

For any ρ ⩾ 1, if there is a polynomial-time ρ-approximationalgorithm for edge dominating set, then there exists a polynomial-time (2ρ − 1)-approximation algorithm for min vertex cover.

Proof

We will show that for each instance G = (V, E) of min vertex cover, we can construct at most |V| instances G _i = (V _i , E _i ) (where |V _i | ⩽ 3|V|) of edge dominating set such that a (2ρ − 1)-approximation solution to G can be found in polynomial time based on a ρ-approximation solution to each G _i . For each positive integer 1 ⩽ i ⩽ |V|, the graph G _i = (V _i , E _i ) is a graph constructed from G in the following way: $V_{i}=V\cup \{a_{j},a^{\prime }_{j}: j\in \{1,\dots , i\}\}$ and E _i = E ∪ F _i ∪ H _i , where $F_{i}=\{(a_{j},a^{\prime }_{j}): j\in \{1,\dots , i\}\}$ and H _i = {(v, a _j ):v ∈ V, j ∈ {1, … , i}}. Informally, G _i contains a copy of G, an induced matching F _i and a complete bipartite graph between the vertices of G and the left part of the induced matching F _i . In Fig. 1 an illustration of the construction of G _i for i = 2 isgiven.

Fig. 1

An illustration of the construction of G _i for i = 2

We first show that a ρ-approximation solution to G _τ implies a (2ρ − 1)-approximation solution to G, where τ is the size of a minimum vertex coverof G.

Let $M^{*}_{\tau }$ and $C^{*}_{\tau }$ be a minimum edge dominating set and a minimum vertex cover of G _τ respectively. Since G _τ contains τ independent edges F _τ , we know that $|M^{*}_{\tau }|\geqslant \tau$. On the other hand, a perfect matching between C ^∗ and {a ₁,⋯ , a _τ } is an edge dominating set of size τ of G _τ . We so have:

$$\begin{array}{@{}rcl@{}} |M^{*}_{\tau}| = \tau. \end{array} $$

(2)

Let M _τ be a ρ-approximation edge dominating set of G _τ and U _τ = V(M _τ ) ∩ V(G). We can see that U _τ is a vertex cover of G. Since M _τ is an edge dominating set of G _τ and F _τ is a set of τ independent edges in G _τ , we know that V(M _τ ) contains at least τ vertices in V(F _τ ). Therefore, we have:

$$\begin{array}{@{}rcl@{}} |U_{\tau}|\leqslant 2|M_{\tau}|-\tau. \end{array} $$

(3)

By combining the fact that $|M_{\tau }|\leqslant \rho |M_{\tau }^{*}|$ together with (2) and (3), we get:

$$\begin{array}{@{}rcl@{}} |U_{\tau}|\leqslant 2|M_{\tau}|-\tau\leqslant 2\rho |M_{\tau}^{*}|-\tau=(2\rho-1)\tau. \end{array} $$

(4)

Therefore, U _τ is a vertex cover of size at most (2ρ − 1)τ of G.

However, we cannot construct G _τ in polynomial time directly, since it is NP-hard to compute the size of the minimum vertex cover τ. To handle this problem, we compute M _i and U _i for each G _i with i ∈ {1, ⋯ ,|V(G)|}, and return U _i∗ such that $|U_{i^{*}}|\leqslant \min _{i=1}^{|V(G)|}\{|U_{i}|\}$ and i ^∗ ∈ {1, ⋯ ,|V(G)|}. Hence, by (4), U _i∗ is a vertex cover of G with size $|U_{i^{*}}|\leqslant |U_{\tau }|\leqslant (2\rho -1)\tau$. □

It is NP-hard to approximate min vertex cover within any factor smaller than $10\sqrt {5}-21$ by a result of Dinur and Safra [9]. By this result and Theorem 1, we get the following corollary.

Corollary 1

For any ε > 0, edge dominating set is not $(5\sqrt {5}-10+\varepsilon )$ -approximable in polynomial time unless P = NP.

Note that under UGC, since min vertex cover cannot be approximated to within 2 − ε for any ε > 0 [16], we get that for any ε > 0, edge dominating set is not (3/2 − ε)-approximable in polynomial time, which is the same lower bound recently achieved in [19].

3 A Simple Parameterized Approximation Schema

In this section, we design a simple parameterized approximation schema for edge dominating set. As mentioned in Introduction, this algorithm contains the basic idea upon which the improved algorithms in Section 4 is built.

3.1 Constrained Edge Dominating Set

First of all, we introduce a constrained edge dominating set problem and present some properties for it. Given a graph G = (V, E) and a prescribed subset V ₁ ⊆ V of non-isolated vertices, an edge dominating set M is called a constrained edge dominating set of G, if V ₁ ⊆ V(M). In the constrained edge dominating set problem, we are asked to find a constrained edge dominating set of minimum size. constrained edge dominating set is a natural generalization of edge dominating set where V ₁ = ∅. We show a simple approximation algorithm for constrained edge dominating set.

Lemma 1

For an instance (G, V ₁) of constrained edge dominating set, let M ₁ be a maximum matching in the induced graph G[V ₁], M ₂ be a maximum matching in the induced graph G[V − V ₁], and M ₃ be a set of |V ₁ − V(M ₁ )| edges such that each edge in M ₃ is incident on a different vertex in V ₁ − V(M ₁ ). Edge set M′ = M ₁ ∪ M ₂ ∪ M ₃ is a constrained edge dominating set with size |M′ | ⩽ (2 − ρ ₁ )ν, where ν is the size of a minimum constrained edge dominating set M ^∗ and ρ ₁ ν is the number of edges in M ^∗ with both endpoints in V ₁.

Proof

Let α ₁, α ₂ and α ₃ be, respectively, the numbers of edges of M ^∗ with both endpoints in V ₁, one endpoint in V ₁ and the other one in V − V ₁, and both endpoints in V − V ₁. Since V ₁ ⊆ V(M ^∗), we have 2α ₁ + α ₂ = |V ₁| = 2|M ₁| + |M ₃|. Since M ₁ is a maximum matching in G[V ₁], $|M_{1}|\geqslant \alpha _{1}$. Note finally that for each edge in M ₂ at least one of its endpoints has to be in V(M ^∗), and then $\alpha _{2}+2\alpha _{3}\geqslant |M_{2}|$.

From these inequalities, we obtain 2|M ₁| + |M ₂| + |M ₃| ⩽ 2|M ^∗|, and then |M′| ≤ (2 − ρ ₁)ν since $|M_{1}|\geqslant \alpha _{1}=\rho _{1}\nu$. □

Note that Lemma 1 is a special case of Lemma 3 in the next section (but we prefer to give a proof of both lemmas for readability). Note also that Lemma 1 implies a 2-approximation algorithm for constrained edge dominating set, with a better ratio obtained when the set V ₁ is large.

3.2 A Parameterized Approximation Schema for edge dominating set

As already mentioned in introduction, deciding whether a graph contains an edge dominating set of size k can be done in O ^∗(2.3147^k) time by the parameterized algorithm presented in [21]. Here we design a parameterized approximation algorithm for it. It is based on the following property:

Property 1

Suppose that there are a set V ₁ and an edge dominating set M such that V ₁ ⊆ V(M), |M| ⩽ k and |V ₁ | = k + ρ′k. Then the number of edges in M that have both endpoints in V ₁ is at least ρ′ k.

Indeed, if there were α < ρ′k edges in M with both endpoints in V ₁, then the number of vertices in V ₁ would be at most 2α + (|M| − α) ⩽ |M| + α < k + ρ′k = |V ₁|, a contradiction. Together with Lemma 1, this means (taking M = M ^∗) that the computed edge set M′ is of size at most (2 − ρ′)k.

Then, our goal is to find such a large set V ₁. As in several articles devising FPT algorithms for edge dominating set, we can use the fact that V(M ^∗) for a minimum edge dominating set M ^∗ is a vertex cover of G. For each edge in the graph, at least one endpoint of it is in V(M ^∗). Then, we can use a branching algorithm to construct a set V ₁ of size up to k + ρ′k such that V ₁ is part of the vertex set of a minimum edge dominating set V(M ^∗) in G. We iteratively select an edge (a, b) in the current graph and branch into two branches by including either a or b into V ₁ and delete it from the graph until the size of V ₁ is k + ρ′k or the remaining graph has no edge. This process produces at most $2^{k+\rho ^{\prime } k}$ vertex sets V ₁ of size at most k + ρ′k in $O^{*}(2^{k+\rho ^{\prime } k})$ time and at least one of them is contained in V(M ^∗). For each of the vertex sets V ₁, we use the algorithm in Lemma 1 to compute M′ and return a smallest one. Using Property 1, the returned edge set is an edge dominating set of size at most (2 − ρ′)k if |M ^∗| ⩽ k (note that if in a leaf of the search tree we have a set V ₁ ⊆ V(M ^∗) with |V ₁| < k + ρ′ k, this means that the remaining graph is empty and the output solution is then optimal by Lemma 1). By taking ρ′ = 1 − ρ, we deduce the followingresult.

Lemma 2

For any ρ > 0, there exists a (1 + ρ)-approximation algorithm to k-edge dominating set running in O ^∗(2^(2−ρ)k ) time for 0 ⩽ ρ ⩽ 1.

When ρ = 0, Lemma 2 implies that k-edge dominating set can be solved in O ^∗(4^k) time, which is far away from the current best parameterized algorithm of running time O ^∗(2.3147^k). To reduce the gap, we will improve the running time bound of our parameterized approximation schema in the next section.

4 Improved Parameterized Approximation Schemata

In the algorithm presented in Section 3.2, in order to search V ₁ we may need to branch on each edge. One way to reduce the running time is to reduce the number of branchings in the algorithm. This approach has been used for (exact) FPT algorithms to obtain improved running times. We will use some of these improved branchings, but we need to combine them with approximability. We first deal with these approximation properties in Section 4.1 and then present the improved parameterized approximation algorithm in Section 4.2.

4.1 More Approximation Algorithms for constrained edge dominating set

Given a graph G = (V, E). We consider a partition (V ₁, V ₂, V ₃) of the vertex set V such that:

• Each connected component of the induced graph G[V ₂] is a clique; and

• There is no edge between a vertex in V ₂ and a vertex in V ₃.

Once the set V ₁ is given, we can find in linear time the set of connected components of G[V − V ₁] which are cliques and which constitute V ₂. Let us now give more properties of our problems based on this partition.

We consider an instance (G = (V, E), V ₁) of constrained edge dominating set. Let M ^∗ be a minimum constrained edge dominating set of (G = (V, E), V ₁) and ν = |M ^∗|.

We denote by α ₁ (resp., α ₂, α ₃) the number of edges in M ^∗ with both endpoints in V ₁ ∪ V ₂ (resp., with one endpoint in V ₁ and one in V ₃, both endpoints in V ₃). This partitions the edge set E into three sets, hence, ν = α ₁ + α ₂ + α ₃.

Moreover, since the connected components of G[V ₂] are cliques and V(M ^∗) is a vertex cover of G, we know that V(M ^∗) contains at least |C _i | − 1 vertices in each clique C _i of G[V ₂]. Assume that there are p cliques C ₁,⋯ , C _p in G[V ₂] among which q cliques Q ₁,⋯ , Q _q are such that V(Q _i ) ⊆ V(M ^∗). Then V(M ^∗) ∩ V ₂ = |V ₂| − p + q. In other words, we have:

$$2\alpha_{1}+\alpha_{2}=|V(M^{*})\cap (V_{1}\cup V_{2})| = |V_{1}| + |V_{2}|-p+q. $$

(5)

We are ready now to specify an approximation algorithm for constrained edge dominating set (Algorithm ApproxPoly1 in Fig. 2), which is a generalization of the algorithm in Lemma 1.

Fig. 2

Algorithm ApproxPoly1

Lemma 3

Edge set M = ApproxPoly1 (G) is a constrained edge dominating set of (G, V ₁ ) with size |M| ⩽ (2 − ρ ₁ )ν, where ρ ₁ ν=α ₁ is the number of edges in M ^∗ with both endpoints in V ₁ ∪ V ₂.

Proof

We first show that M is a constrained edge dominating set. It is easy to see that M′=M ₁ ∪ M ₂ ∪ M ₃ is an edge dominating set and each vertex in V ₁ will appear in at least one edge in M ₁ ∪ M ₃. When we remove an edge $e=(u,c^{\prime }_{i})\in M^{\prime }_{1}$ with $c^{\prime }_{i}\in V^{\prime }_{2}$ from M′, we know by Step 3 of the algorithm that every other neighbor w of u is saturated by M ₁. Hence, the edge (u, w) incident to u is still dominated and then M is still an edge dominating set. Furthermore vertex u is not in V ₁ and we know that M is a constrained edge dominating set.

Now we prove the claim on the size of M. By the construction, we know that the size of the maximum matching in $G[V_{1}\cup V_{2}\cup V^{\prime }_{2}]$ is at least α ₁ + p − q (take the α ₁ edges of M ^∗ in V ₁ ∪ V ₂, and add the p − q edges between an unsaturated vertex in a clique of G[V ₂] and the corresponding vertex $c^{\prime }_{i}$). Then, we get $|M_{1}|\geqslant \alpha _{1}+p-q \label {lem1_1}$.

Since each edge in $M_{1}-M^{\prime }_{1}$ contains two vertices in V ₁ ∪ V ₂, each edge in $M_{3}\cup M^{\prime }_{1}$ contains one vertex in V ₁ ∪ V ₂, and all of these vertices are different, it holds that

$$2|M_{1}| + |M_{3}|-|M^{\prime}_{1}| = 2(|M_{1}|-|M^{\prime}_{1}|)+(|M_{3}| + |M^{\prime}_{1}|)\leqslant |V_{1}| + |V_{2}|.$$

Therefore:

$$ |M_{1}| + |M_{3}|-|M^{\prime}_{1}| \leqslant |V_{1}| + |V_{2}|-p+q-\alpha_{1} = 2\alpha_{1}+\alpha_{2}-\alpha_{1}=\alpha_{1}+\alpha_{2}. ~~~~~~~ (b\mathit{y}(5)) $$

(6)

Note that there are at most α ₂ + 2α ₃ different vertices in V(M ^∗) ∩ V ₃. Then:

$$ |M_{2}|\leqslant \alpha_{2}+2\alpha_{3}. $$

(7)

Summing (6) and (7), we get $|M| = |M_{1}| + |M_{2}| + |M_{3}|-|M^{\prime }_{1}|\leqslant \alpha _{1}+2\alpha _{2}+2\alpha _{3}=(2-\rho _{1})\nu$. □

Note that Lemma 1 is a special case of Lemma 3 where the vertex set V ₂ is an empty set. Lemma 3 shows that we do not need to branch on each clique component in G[V − V ₁] in order to search the vertex set of a constrained edge dominating set.

To improve the running time of our parameterized approximation schema, we also need to consider a particular case of the graph where in the partition (V ₁, V ₂, V ₃) each connected component of G[V ₃] is a path of length 2.

Let N be the number of these paths in G[V ₃]. Considering a minimum constrained edge dominating set M ^∗, we denote by:

• N ₁ the set of paths in G[V ₃] such that there is an edge in M ^∗ between a vertex in V ₁ and the central vertex of the path; set n ₁ = |N ₁|;

• N ₂ the set of paths in G[V ₃] such that there is an edge of the path in M ^∗; set n ₂ = |N ₂|; and

• N ₃ the set of remaining paths in G[V ₃]; set n ₃ = |N ₃|.

Observe that some paths of G[V ₃] may be counted twice (one with N ₁ and one with N ₂, if M ^∗ is not a matching); so, N ⩽ n ₁ + n ₂ + n ₃. Note that for each of the n ₃ remaining paths, M ^∗ has to take two edges (between V ₁ and the endpoints of the path) to cover the edges of the path. In other words, $\alpha _{2}\geqslant 2n_{3}+n_{1}$. Moreover, by definition, n ₂ ⩽ α ₃.

Consider Algorithm ApproxPoly2 (Fig. 3) on an instance (G, V ₁) of constrained edge dominating set.

Fig. 3

Algorithm ApproxPoly2

Lemma 4

Edge set M = ApproxPoly2 (G) is a constrained edge dominating set of (G,V ₁ ) with size |M| ⩽ ν + n ₃.

Proof

The fact that M is a constrained edge dominating set can be obtained similarly as in the proof of Lemma 3. We only need to prove the claim on the size of M.

Let us denote by γ ₁ (resp., γ ₂) the number of edges of M ₁ that have both endpoints in V ₁ ∪ V ₂ (resp., one endpoint in V ₁, the other one being a central vertex of a path in V ₃). Then, $|M_{1}| = \gamma _{1}+\gamma _{2}+|M^{\prime }_{1}|$.

By the construction, we know that the size of the maximum matching in $G[V_{1}\cup V_{2}\cup V^{\prime }_{2}\cup V^{\prime }_{3}]$ is at least α ₁ + n ₁ + p − q. Then we get: $|M_{1}| = \gamma _{1}+\gamma _{2}+|M^{\prime }_{1}| \geqslant \alpha _{1}+n_{1}+p-q$. We also have $2\gamma _{1}+\gamma _{2}+|M^{\prime }_{1}| + |M_{3}|\leqslant |V_{1}| + |V_{2}|$, which is equivalent to $\gamma _{1}+|M_{3}|\leqslant |V_{1}| + |V_{2}|-\gamma _{1}-\gamma _{2}-|M^{\prime }_{1}|$. Therefore:

$$ \gamma_{1}+|M_{3}| \leqslant |V_{1}| + |V_{2}|-p+q-\alpha_{1}-n_{1} = 2\alpha_{1}+\alpha_{2}-\alpha_{1}-n_{1}=\alpha_{1}+\alpha_{2}-n_{1} ~~~~(b\mathit{y}(5)) $$

(8)

Note that γ ₂ + |M ₂| = N, N ⩽ n ₁ + n ₂ + n ₃ ⩽ n ₁ + α ₃ + n ₃ and ν = α ₁ + α ₂ + α ₃. We get:

$$\begin{array}{@{}rcl@{}} &&|M| = |M_{1}| + |M_{2}| + |M_{3}|-|M^{\prime}_{1}| = \gamma_{1}+\gamma_{2}+|M_{2}| + |M_{3}| = \gamma_{1}+|M_{3}|+N\\ &&\leqslant \alpha_{1}+\alpha_{2}-n_{1}+N ~~~~~~~ (b\mathit{y}~(8))\\ &&\leqslant \nu+n_{3}. \end{array} $$

that concludes the proof of the lemma. □

4.2 An Improved Parameterized Approximation Schema

Now we are able to give the improved parameterized approximation schema ApproxFPT for k-edge dominating set as well as k-constrained edge dominating set. As explained earlier, the principle is to search the vertex set V ₁ by using some ‘good’ branchings. Then, in each leaf of our search tree, we will use the approximation algorithms devised in Section 4.1 (either directly, or after someother steps).

We consider a k-constrained edge dominating set (G, V ₁) with partition I = (V ₁, V ₂, V ₃) of the vertex set. Let t = |V ₁| + |V ₂| − p (where p is the number of cliques in G[V ₂]). When $t\geqslant (2-\rho )k$ (0 ⩽ ρ ⩽ 1), there are at least (1 − ρ)k edges in any optimal solution M ^∗ with both endpoints in V ₁ ∪ V ₂. Therefore, Lemma 3 implies that a (1+ρ)-approximation solution to k-constrained edge dominating set can be found in polynomial time, if $t\geqslant (2-\rho )k$. We will use a branch-and-search method to move vertices from V ₃ to V ₁ ∪ V ₂ and therefore to increase the parameter t. Note that for each vertex v ∈ V ₃, it is either in V(M ^∗) or not. For the second case, all neighbors of v should be in V(M ^∗) since V(M ^∗) is a vertex cover of the graph. Then, we can branch on v by either moving v into V ₁ (this means v ∈ V(M ^∗)) or by moving the neighbor set N(v) of v in G[V ₃] into V ₁ (this means v ∉ V(M ^∗)) and moving all newly created clique components in G[V ₃] into V ₂. When v is a vertex of degree $\geqslant 3$ in G[V ₃], we can branch with recurrence:

$$\begin{array}{@{}rcl@{}} C(t)\leqslant C(t+1)+C(t+3), \end{array} $$

(9)

where C(t) is the worst size of the search tree in the algorithm when the current value of |V ₁| + |V ₂| − p is t. When the maximum degree of G[V ₃] is at most 2, we may only get:

$$C(t)\leqslant C(t+1)+C(t+2), $$

by branching on a maximum degree vertex. In fact, there are some techniques to branch on a component H in G[V ₃] with a recurrence not worse than (9), if H is not a path of length 2 [20, 21, 23].

For a path p ₁ p ₂ p ₃ p ₄… of length at least 3, we can branch on p ₃ by including it into V ₁ or including its neighbors p ₂ and p ₄ into V ₁. For the first branch, we will also move a clique component p ₁ p ₂ into V ₂. Then we can get:

$$ C(t)\leqslant C(t+2)+C(t+2), $$

(10)

which is better than (9).

For a cycle of length at least 5, we branch on an arbitrary vertex in the cycle and then branch on the generated paths in each branch and finally we can get a recurrence not worse than (9). For a cycle c ₁ c ₂ c ₃ c ₄ of length 4, we can also branch with (10) by including either {c ₁, c ₃} or {c ₂, c ₄} into V ₁. For the details about the proof of this fact, reader is referred to [20, 21, 23].

It turns out that only for a component of path of length 2 in G[V ₃] we cannot branch with a recurrence as good as (9). We will call a branching with recurrence at least as (9) a good branching.

The main steps of the improved parameterized approximation schema ApproxFPT are listed in Fig. 4.

Fig. 4

Algorithm ApproxFPT

Theorem 2

Let ρ ^⋆ ≃ 0.21 be such that $1.466=1.619^{(1-\rho ^{\star })}$. Then, for any ρ with 0 ⩽ ρ ⩽ 1, ApproxFPT is a (1 + ρ)-approximation algorithm running in time O ^∗(2.374^(1−ρ)k ) if ρ ⩽ ρ ^⋆ and in time O ^∗(1.466^(2−ρ)k ) if ρ ⩾ ρ ^⋆.

Proof

In order to prove the running time claimed, we will prove more generally that in an instance I the algorithm works in time:

• O ^∗(1.466^{(2 − ρ)k − t(I)}) if $\rho \geqslant \rho ^{*}$;

• O ^∗(1.466^{(1 − ρ)k − t(I)}1.619^{(1 − ρ)k}) if ρ ≤ ρ ^∗.

Then, the result follows since $t(I)\geqslant 0$ and 1.466 × 1.619 < 2.374.

Note also that the positive root of 1 = x ⁻¹ + x ⁻³ is 1.4655 … < 1.466 and that of 1=x ⁻¹+x ⁻² is 1.6180 … < 1.619.

Consider so the different steps of the Algorithm ApproxFPT:

• Step 1: when branching, in one branch (1 − ρ)k − t(I) reduces by at least 1, and in the other branch (1 − ρ)k − t(I) reduces by at least 3, so the recurrence is verified.

• Steps 2 and 3: the running time is polynomial, which verifies the claim since when we branch we have t(I) ⩽ (2 − ρ)k (the validity for ρ ⩽ ρ ^∗ follows from the fact that in this case 1.466 ⩽ 1.619^{(1 − ρ)k}, hence a polynomial is indeed O ^∗(1.466 ^{− k}1.619^{(1 − ρ)k})).

• Step 4: we directly compute the running time in this node. We build a tree where at each branching t(I) increases by 1 in one branch and by two in the other branch. We stop when t(I) reaches 2(1 − ρ)k (or before if V ₃ becomes empty). Then, the number of leaves in this tree is (at most) 1.619^{2(1 − ρ)k − t(I)}. For $\rho \geqslant \rho ^{*}$, 1.619^{1 − ρ} ⩽ 1.466; so, the bound on the running time is valid. For ρ ⩽ ρ ^∗, since $t(I)\geqslant (1-\rho )k$, 1.619^{2(1 − ρ)k − t(I)} ⩽ 1.619^{(1 − ρ)k}1.466^{(1 − ρ)k − t(I)}. Then, the running time in this node verifies the claim.

• Step 5: the running time is polynomial and verifies the claim.

• Step 6: the running time is O ^∗(2^{2(1 − ρ)k/3})=O ^∗(1.6^{(1 − ρ)k}) which verifies the claim since in this step t(I) ⩽ (1 − ρ)k.

• Step 7: let $z=\sum _{i=0}^{(1-\rho )K-N}{N \choose i}$. The running time is O ^∗(z). Let P = (1 − ρ)k − N. Then $z=\sum _{i=0}^{P}{(1-\rho )k-P \choose i}$. But P = (1 − ρ)k − N ⩽ (1 − ρ)k/3. Then z ⩽ 1.619^{(1 − ρ)k} [21]. This verifies the claim since t(I) ⩽ (1 − ρ)k.

Let us now prove the approximation ratio claimed. Since Algorithms ApproxPoly1 (G) and ApproxPoly2 (G) will return a constrained edge dominating set, ApproxFPT (G, k, ρ) will also return a constrained edge dominating set.

In order to prove the ratio claimed, we assume that the size ν of the optimal solution is not greater than k and consider all the possible cases.

• If $t=|V_{1}| + |V_{2}|-p\geqslant (2-\rho )k$, then we have $2\alpha _{1}+\alpha _{2}\geqslant t\geqslant \alpha _{1}+\alpha _{2}+\alpha _{3}+(1-\rho )k$ and, consequently, $\alpha _{1}\geqslant (1-\rho )k$. Using Lemma 3, we get |ApproxPoly1(G)| ⩽ (1+ρ)k.

• Assume ρ ≥ 1/2. If α ₂ > k, then the size of the optimal solution is greater than k. Else, we have that |ApproxPoly2(G)| ⩽ k + n ₃ ⩽ k + α ₂/2 ⩽ 3k/2 ⩽ (1 + ρ)k.

• In Step 4, we consider the two stop conditions V ₃ = ∅ and $t\geqslant 2(1-\rho )k$ in Step 4(b). For the former, we know from Lemma 4 that ApproxPoly2(G) returns an optimal solution. For the latter, in the current graph we have $k+\alpha _{1}\geqslant t >2(1-\rho ) k$, and $2\rho k>k-\alpha _{1}\geqslant \alpha _{2}$ (by $k\geqslant \nu \geq \alpha _{1}+\alpha _{2}$). Then n ₃ ⩽ α ₂/2 < ρ k and Lemma 4 gives |ApproxPoly2(G)| ⩽ k + n ₃ ⩽ (1 + ρ)k.

• In Step 5, we have $N\geqslant (1-\rho )k$. But n ₁ + n ₂ + 2n ₃ ⩽ ν ⩽ k, meaning that n ₃ ⩽ k − N ⩽ ρ k. Again, Lemma 4 gives |ApproxPoly2(G)| ≤ k + n ₃ ≤ (1+ρ)k.

• In Step 6, for each branch V ₃ = ∅ and ApproxPoly2(G) returns the optimal solution under the current condition.

• For the last step, let G be the graph before executing any operations in Step 7 and n ₃ be the size of N ₃ in G. Let S ₁ be N ₃ if |N ₃| ≤ (1 − ρ)k − N, and S ₁ be a subset of N ₃ of size (1 − ρ)k − N otherwise. Then, S ₁ is a subset of size at most (1 − ρ)k − N that will be considered in Step 7. We only need to show that in the branch where S ₁ is considered, we can get a feasible solution within the approximation ratio. Let G′ be the graph after removing S ₁ out of V ₃ (before running ApproxPoly2(G)) in Step 7 and n′ be the size of N ₃ in G′. By definition, we have that n ₃ + N ⩽ ν ⩽ k, and then n ₃ ⩽ k − N. Note that $n^{\prime }_{3}\leqslant \max (0,n_{3}-((1-\rho )k-N)\leqslant \rho k$. Therefore, $|\texttt {ApproxPoly2}(G^{\prime })|\leqslant k+n^{\prime }_{3}\leqslant (1+\rho )k$.

The proof of the lemma is now completed. □

5 Parametrization by the Vertex Cover Number

Since the size of any vertex cover in a graph is at least the size of any matching in this graph, any parameterized algorithm for edge dominating set working in O(f(k)|I|^O(1)) time also works in O(f(τ)|I|^O(1)) time, where τ is the size of the minimum vertex cover of the graph. Hence, it is possible to solve edge dominating set within time O ^∗(2.3147^τ) by using the algorithm in [21]. In this section we show that this result can be improved down to O ^∗(1.821^τ).

To this aim, let us consider the algorithm FPT _τ presented in Fig. 5, which outputs a minimum edge dominating set in graph G. Let α≃0.2864 be such that $2.3147^{\alpha }=\left (\frac {1}{\alpha ^{\alpha }(1-\alpha )^{1-\alpha }}\right )$.

Fig. 5

Algorithm FPT _τ

Theorem 3

FPT _τ (G) computes a minimum edge dominate set in O ^∗(1.821^τ ) time.

Proof

We first show that the algorithm returns a minimum edge dominating set. If there exists an edge dominating set of size at most (1 − α)τ(G), it will be found in Step 2 of the algorithm. Suppose now that this is not the case, and let M′ be an arbitrary maximal matching. Note that each edge of M′ has at least one of its endpoint in V ^∗. In other words, $|V^{*}\cap V(M^{\prime })|\geqslant |M^{\prime }|$, meaning that

$$|V^{*}\setminus V(M^{\prime})|\leqslant |V^{*}|-|M^{\prime}|\leqslant \alpha \tau.$$

Therefore, the set V ^∗∖V(M′) is of size at most α τ and will be considered in Step 3. We look at the case that V ₁ = V ^∗∖V(M′). Now V ₂ = V ^∗ ∩ V(M′). Moreover, we have the two following properties:

• 1. V ₂ ∪ S ₁ is a vertex cover of G;

• 2. V ₂ ∪ S ₁ is included in V(M′).

To see the first property, remark that S ₂ is an independent set. Moreover, V ₁ is also an independent set (if there were an edge in V ₁ then, one of its endpoints should be in V(M′), a contradiction with the considered case). Finally, there is no edge between a vertex of V ₁ and a vertex of S ₂ by definition of S ₁.

We already know that V ₂ ⊆ V(M′). Each vertex v ∈ S ₁ is adjacent to a vertex w ∈ V ₁. Since w ∉ V(M′), we know that necessarily v ∈ V(M′). The second property follows.

From the first property we deduce that the set M′ (V ₁) is an edge dominating set. Let m ₁ = |M(V ₁)|. We have |M′ (V ₁)| = m ₁ + (|V ₂| + |S ₁| − 2m ₁). But M′ has $m^{\prime }_{1}\leqslant m_{1}$ edges with both endpoints in V ₂ ∪ S ₁. By the second property, $|M^{\prime }|\geqslant m^{\prime }_{1}+(|V_{2}| + |S_{1}|-2m^{\prime }_{1})\geqslant m_{1}+(|V_{2}| + |S_{1}|-2m_{1})=|M^{\prime }(V_{1})|$, which implies that M′ (V ₁) is a minimum edge dominating set.

We now analyze the running time of Algorithm FPT _τ . Step 1 can be done in O ^∗(1.2738^τ) time [7]. If an edge dominating set has been found in Step 2, then the running time is:

$$O^{*}\left(2.3147^{(1-\alpha)\tau}\right)=O^{*}\left(1.821^{\tau}\right). $$

Otherwise, by Stirling’s Formula, we know that the number of subsets of V ^∗ of size at most α τ is $O^{*}\left (\left (\frac {1}{\alpha ^{\alpha }(1-\alpha )^{1-\alpha }}\right )^{\tau }\right )=O^{*}(1.821^{\tau })$. □

6 Conclusion

We provide in this article new insights on the approximability of edge dominating set. Our parameterized approximation algorithm first apply some steps of a branching algorithm, and then exploit the specificity of obtained instances to get an approximate solution on them. This is rather different from the notions of fidelity preserving transformation recently introduced in [11] where informally the instance is first reduced in an approximate way (and then an (exact) FPT algorithm is applied). In particular, our approximation algorithm relies on the branching steps; this is not the case in the approach of [11] and applying this latter approach for edge dominating set is an interesting open question mentioned in [11]. Moreover, our algorithm has complexity $O^{*}(\gamma _{\rho }^{k})$ for a ratio ρ where γ ₁ = 2.374 (exact algorithm) and γ ₂ = 1.466. Since achieving a ratio 2 is polynomial, one could hope to find approximation algorithms where γ _ρ → 1 when ρ → 2, which we leave as open question.