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

<ul>
<li>Bourgeois, N., Escoffier, B., Paschos, V. T., &amp; van Rooij, J. M. (2012). Fast algorithms for max independent set. Algorithmica, 62(1-2), 382-415.</li>
</ul>

<p>Moreover, the following paper proves a hardness result for an (<span class="math-container">$1+\epsilon$</span>) approximation algorithm for vertex cover in cubic graphs.</p>

<ul>
<li>Alimonti, P., &amp; Kann, V. (1997, March). Hardness of approximating problems on cubic graphs. In Italian Conference on Algorithms and Complexity (pp. 288-298). Springer, Berlin, Heidelberg.</li>
</ul>

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

CC BY-SA 4.0
2018-11-22T21:44:01.960Z
The paper by Bourgeois et al. that you mention actually provides better running time bounds for cubic graphs (average degree 3).
Christian Komusiewicz
CC BY-SA 4.0
2019-09-16T20:41:49.517Z
Specifically, in the abstract of the Bougeois et al. paper, they mention a $O^*(1.0854^n)$ algorithm for graphs with average degree 3.
isaacg
CC BY-SA 4.0
2018-11-22T20:32:05.467Z
2018-11-22T20:32:05.467Z
Mohemnist
<p>In the approximation algorithms side, there is an <span class="math-container">$(2-2/\Delta)$</span>-approximation <a href="https://www.sciencedirect.com/science/article/pii/0166218X8390080X" rel="nofollow noreferrer">algorithm</a> by Hochbaum where <span class="math-container">$\Delta$</span> 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. </p>

CC BY-SA 4.0
2019-09-14T10:52:04.963Z
2019-09-14T10:52:04.963Z
A.2
<p>"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.</p>

<cc.complexity-theory><ds.algorithms><np-hardness><complexity-classes><approximation-algorithms>
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
Dabbler
# What is the best approximation and exact algorithm for vertex cover on cubic graphs?

(Asked by: username_0 on 2018-06-19)

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

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, complexity-classes, approximation-algorithms

---

## 2 answers

### Answer by username_1 on 2018-11-22. Score: 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.

> **Comments:**
> **username_2**: The paper by Bourgeois et al. that you mention actually provides better running time bounds for cubic graphs (average degree 3).  
> **username_3**: Specifically, in the abstract of the Bougeois et al. paper, they mention a $O^*(1.0854^n)$ algorithm for graphs with average degree 3.  

---

### Answer by username_4 on 2019-09-14. Score: 1

In the approximation algorithms side, there is an $(2-2/\Delta)$-approximation [algorithm](https://www.sciencedirect.com/science/article/pii/0166218X8390080X) 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.


---

