Summary: We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere $ϵ$-dense and average [‘$(e)$]-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 $\overlineϵ$-dense graphs by using the techniques of Karpinski and Zelikovsky, the approximation ratios of min $\{2,3/(1 + 2ϵ)\}$ and of $\min\{2,3/(3-2\sqrt{1-\overlineϵ})\}$, respectively. On the other hand, we show that it is UGC-hard to approximate the Minimum Edge Dominating Set problem in everywhere $ϵ$-dense graphs with a ratio better than $2/(1 + ϵ)$ with $ϵ> 1/3$ and $2/(2-\sqrt{1-\overlineϵ})$ with $\overlineϵ> 5/9$ in average [‘$(e)$]-dense graphs.