Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2010 Copyright 2010 Universität Bonn, Institut für Informatik, Abt. V
89122

18.02.2010

On Approximation Complexity of Edge Dominating Set Problem in Dense Graphs
Richard Schmied and Claus Viehmann
[Download PostScript] [Download PDF]

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 min{2,3/(3-2\sqrt{1-ε})}, 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/2 and 2/(2-\sqrt{1-ε}) with ε ≥ 3/4 in average ε-dense graphs.

Last Change: 11/05/14 at 10:54:19
 English
Universität Bonn -> Institut für Informatik -> Abteilung V