# Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

The paper [Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Austrin, Khot, Safra] Shows that assuming the Unique Game Conjecture (UGC) the minimum vertex cover problem cannot be approximated to within a factor $$2-(2+o_d(1)) \cdot \frac{\log \log d}{\log d}$$. However, it is not clear to me if this result or any other result gives a concrete lower bound on the approximability of minimum vertex cover where the graph is 3-regular (or 3-bounded degree) assuming UGC or any other well-known complexity assumption. Any help would be appreciated.

• My understanding is that we don't have such a concrete lower bound. The question is not particularly about three, but we don't have a concrete lower bound for 4, 5, or any fixed constant. Indeed, any lower bound for 4-regular graphs can imply one for cubic graphs (using the reduction in doi.org/10.1016/S0304-3975(98)00158-3). If it can be found, such a concrete bound must be very small (close to one). Commented Apr 6 at 8:25
• Presumably $d$ is the max degree? @YixinCao, doesn't the paper you link to show that the problem is APX-hard , answering OP's question? (Presumably the underlying constant can be calculated with some work...) And BTW a reference that paper cites seems to show that the problem admits a 1.167-approximation algorithm for $d=3$. Commented Apr 14 at 0:44
• @NealYoung Apparently, OP knew the APX-hardness and was asking for the specific number, like 2 for vertex cover without degree restrictions (assuming the UGC). If we have the bound for graphs of degrees at most four, then the cited paper can give the number for cubic graphs (=3 or at most 3), but it would ask for the bound for graphs of degrees at most five or six... Commented Apr 15 at 9:13