Approximating Edge Dominating Sets in Weighted Graphs (Algorithm Engineering as a New Paradigm)
Toshihiro Fujito · Kyoto University Research Information Repository (Kyoto University) · 1999
We study approximability of the edge dominating set problem.It has been known, besides its $NP$ -hardness, that a solution of size at most twice larger than the smallest one can be efficiently computed, due to its close relationship to minimum maximal matching.In general when graphs are edge weighted, however, such a nice relationship breaks down.and no edge dominating set of small weight is obtainable from any maximal mat,ching.In this paper, after showing that $\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\prime \mathrm{e}\mathrm{d}$ edge domination is as hard to approximate as weighted vertex cover is, we consider two natural strategies, one reducing edge dominating set to vertex cover and the other to edge cover, and show that weighted edge dominating $\mathrm{s}\mathrm{e}\mathrm{t}_{r}$ can be approximated within factors of 4 and $2 \frac{2}{3}$ , respectively.