Approximating edge dominating set in dense graphs

We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere ϵ-dense and average -dense graphs. More precisely, we consider the computational complexity of approximating a generalization of the Minimum Edge Dominating Set problem, the so called Minimum Subset Edge Dominating Set problem. As a direct result, we obtain for the special case of the Minimum Edge Dominating Set problem in everywhere ϵ-dense and average -dense graphs by using the techniques of Karpinski and Zelikovsky, the approximation ratios of min{2,3/(1+2ϵ)} and of , respectively.On the other hand, we give new approximation lower bounds for the Minimum Edge Dominating Set problem in dense graphs. Assuming the Unique Game Conjecture, we show that it is NP-hard to approximate the Minimum Edge Dominating Set problem in everywhere ϵ-dense graphs with a ratio better than 2/(1+ϵ) with ϵ>1/3 and with in average -dense graphs.