Approximating edge dominating set in dense graphs

作者：Schmied Richard; Viehmann Claus^*

来源：Theoretical Computer Science, 2012, 414(1): 92-99.

DOI：10.1016/j.tcs.2011.10.001

• Edge dominating set
• Minimum Maximal Matching
• Dense instances
• Approximation algorithms
• Approximation lower bounds

We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere epsilon-dense and average (epsilon) over bar -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 epsilon-dense and average (epsilon) over bar -dense graphs by using the techniques of Karpinski and Zelikovsky, the approximation ratios of min{2, 3/(1 + 2 epsilon)) and of min{2, 3/(3 - 2 root 1 - (epsilon) over bar)}, respectively. %26lt;br%26gt;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 epsilon-dense graphs with a ratio better than 2/(1 + epsilon) with epsilon %26gt; 1/3 and 2/(2 - root 1 - (epsilon) over bar) with (epsilon) over bar %26gt; 5/9 in average (epsilon) over bar -dense graphs.

• 出版日期2012-1-13