"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$ Nov 22, 2018 at 21:44
-
$\begingroup$ Specifically, in the abstract of the Bougeois et al. paper, they mention a $O^*(1.0854^n)$ algorithm for graphs with average degree 3. $\endgroup$– isaacgSep 16, 2019 at 20:41
$\begingroup$
$\endgroup$
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.
