On Approximating (Connected) 2-Edge Dominating Set by a Tree

摘要

Abstract The edge dominating set problem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and connected dominations combined. In the b -EDS problem, each edge needs to be dominated b times. Connected EDS requires an edge dominating set to be connected while it has to form a tree in Tree Cover . Although each of EDS, b -EDS, and Connected EDS (or Tree Cover ) has been well studied, each known to be approximable within 2 (or 8/3 for b -EDS in general), nothing is known when these extensions are imposed simultaneously on EDS unlike in the case of the (vertex) dominating set problem. We consider Connected 2-EDS and 2-Tree Cover (i.e., a combination of 2-EDS and Tree Cover ), and present a polynomial algorithm approximating each within 2. Moreover, it will be shown that the single tree computed is no larger than twice the optimum for (not necessarily connected) 2-EDS, thus also approximating 2-EDS equally well. It also implies that 2-EDS with clustering properties can be approximated within 2 as well.