# What is the best approximation and exact algorithm for vertex cover on cubic graphs?

"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.

• The paper by Bourgeois et al. that you mention actually provides better running time bounds for cubic graphs (average degree 3). Nov 22 '18 at 21:44
• Specifically, in the abstract of the Bougeois et al. paper, they mention a $O^*(1.0854^n)$ algorithm for graphs with average degree 3. Sep 16 '19 at 20:41

In the approximation algorithms side, there is an $$(2-2/\Delta)$$-approximation algorithm by Hochbaum where $$\Delta$$ is the maximum degree of the graph. This translates to a 1.33-approximation algorithm for cubic graphs. It seems like there hasn't been any improvement over this.