On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem

We consider a multiple domination version of the edge dominating set problem, called the b-EDS problem, where an edge set D subset of E of minimum cardinality is sought in a given graph G = (V, E) with a demand vector b subset of Z(E) such that each edge e is an element of E is required to be dominated by b(e) edges of D. When a solution D is not allowed to be a multi-set, it is called the simple b-EDS problem. We present 2-approximation algorithms for the simple b-EDS problem for the cases of max(e is an element of E)b(e) = 2 and max(e is an element of E) b(e) = 3. The best approximation guarantee previously known for these problems is 8/3 due to Berger et al. [2] who showed the same guarantee to hold even for the minimum cost case and for arbitrarily large b. Our algorithms are designed based on an LP relaxation of the b-EDS problem and locally optimal matchings, and the optimum of b-EDS is related to either the size of such a matching or to the optimal LP value.