Approximating vertex cover on dense graphs
Tomokazu Imamura, Kazuo Iwama · Symposium on Discrete Algorithms · 2005
Although many problems in MAX-SNP admit a PTAS for dense graphs, that is not the case for Vertex Cover, which is MAX-SNP hard even for dense graphs. This paper presents a randomized approximation algorithm for Vertex Cover on dense graphs, i.e., graphs whose average degree d is Ω(n). (i) Our algorithm improves the best-known bound for the approximation factor by Karpinski and Zelikovsky. For example, our bound is 2/1 + d/2Δ for dense graphs such that |E| ≤ Δ(n - Δ) where Δ is the maximum degree. The improvement is especially large when d a Δ; if d ≥ 2/3Δ for instance, our bound is at most 1.5 while the previous bound approaches to 2.0 as n/Δ increases. (ii) It achieves the same factor for a wider range of graphs, i.e., for the graphs whose Δ is Ω(n log log n/log n). (iii) It is probably optimal in the sense that if we can achieve a better approximation factor by δ > 0 for the above range of graphs, then we can achieve a factor of 2 - δ for general graphs.