"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.


The best-known algorithm for vertex cover in (general) graphs runs in time $O(1.2114^n)$ by Bourgeois, Escoffier, Paschos and van Rooij. You may read their paper and see whether their algorithm can be improved for cubic graphs.

  • Bourgeois, N., Escoffier, B., Paschos, V. T., & van Rooij, J. M. (2012). Fast algorithms for max independent set. Algorithmica, 62(1-2), 382-415.

Moreover, the following paper proves a hardness result for an ($1+\epsilon$) approximation algorithm for vertex cover in cubic graphs.

  • Alimonti, P., & Kann, V. (1997, March). Hardness of approximating problems on cubic graphs. In Italian Conference on Algorithms and Complexity (pp. 288-298). Springer, Berlin, Heidelberg.

However, a greedy 2-approximation algorithm for vertex cover in general graphs is easy. Just pick an uncovered edge each time and choose both of its ends.

  • $\begingroup$ The paper by Bourgeois et al. that you mention actually provides better running time bounds for cubic graphs (average degree 3). $\endgroup$ – C Komus Nov 22 '18 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.