Algorithms Seminar 2004

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 which is probably optimal: Let $\varepsilon=\overline{d}/\Delta$ where $\overline{d}$ and $\Delta$ are the average and maximum degrees of a given graph $G$. $G$ is said to be dense if its $\overline{d}$ is $\Omega(n)$. (i)~Our algorithm achieves an approximation factor of $2 - \frac{\varepsilon}{1+\varepsilon/2}$ for dense graphs, which improves the best-known bound by Karpinski and Zelikovsky. For example, it approximates within a factor of 1.334 if the graph is regular. (ii)~It achieves the same factor for a wider range of graphs, i.e., for the graphs whose $\Delta$ is $\Omega(n\frac{\log\log n}{\log n})$. (iii)~It is probably optimal in the sense that if we can achieve a better approximation factor by $\delta > 0$ for the above range of graphs, then we can achieve a factor of $2-\delta$ for general graphs. Joint work with Tomokazu Imamura.