<p>I hope expert researchers don't vote against my answer. Based on your questuon about assuming other complexity assumptions,  I think I could introduce a less than 2 approximation ratio (1.999999) for the vertex cover problem (by introducing a new SDP formulation).
<a href="https://arxiv.org/abs/2403.19680" rel="nofollow noreferrer">https://arxiv.org/abs/2403.19680</a><br />
I know this is contrary to what experts belives about the Unique Games Conjecture. But, I hope they can read my paper and identify any error in it (if there is any error)!</p>

CC BY-SA 4.0
2024-04-14T00:28:40.513Z
I would recommend that If you want this to be taken seriously, publicize it *only* after you publish it in a good peer-reviewed journal.  If it is correct, it should have no problem getting accepted into any of the best journals in theoretical computer science.  Before it has been peer reviewed, people will generally assume it is incorrect, and most likely no one will find it worth their time to read it for you to check the details carefully.  Also, it is not about 3-regular graphs, so your answer seems more like naive self-promotion than an answer to the posted question.
Neal Young
CC BY-SA 4.0
2024-04-14T08:43:26.257Z
@Neal Young. Thank you for your comment. I should say that I submitted it. But, due to critical points of view about this problem, I liked to contact with expert researchers (for presentation of my idea/for collaburation with them to improve the idea).
Majid Zohrehbandian
CC BY-SA 4.0
2024-04-14T21:40:45.150Z
Well, if you must, maybe make a separate post with your own question, rather than piggybacking on a question that is only tangentially related...  Your question seems to be "*is there an error in my paper"*?
Neal Young
CC BY-SA 4.0
2024-04-09T12:41:14.827Z
2024-04-09T12:41:14.827Z
Majid Zohrehbandian
<p>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 <span class="math-container">$2-(2+o_d(1)) \cdot \frac{\log \log d}{\log d}$</span>. 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.</p>

CC BY-SA 4.0
2024-04-06T08:25:48.697Z
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 https://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).
Yixin Cao
CC BY-SA 4.0
2024-04-14T00:44:39.257Z
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](https://doi.org/10.1007/s002240000113) seems to show that the problem admits a  1.167-approximation algorithm for $d=3$.
Neal Young
CC BY-SA 4.0
2024-04-15T09:13:59.583Z
@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...
Yixin Cao
<approximation-hardness><unique-games-conjecture><bounded-degree><vertex-cover>
Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs
John
# Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

(Asked by: username_0 on 2024-04-06)

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.

**Tags:** approximation-hardness, unique-games-conjecture, bounded-degree, vertex-cover

> **Comments:**
> **username_1**: 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 https://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).  
> **username_2**: 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](https://doi.org/10.1007/s002240000113) seems to show that the problem admits a  1.167-approximation algorithm for $d=3$.  
> **username_1**: @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...  

---

## 1 answers

### Answer by username_3 on 2024-04-09. Score: -4

I hope expert researchers don't vote against my answer. Based on your questuon about assuming other complexity assumptions, I think I could introduce a less than 2 approximation ratio (1.999999) for the vertex cover problem (by introducing a new SDP formulation).
<https://arxiv.org/abs/2403.19680>  
I know this is contrary to what experts belives about the Unique Games Conjecture. But, I hope they can read my paper and identify any error in it (if there is any error)!

> **Comments:**
> **username_2**: I would recommend that If you want this to be taken seriously, publicize it *only* after you publish it in a good peer-reviewed journal.  If it is correct, it should have no problem getting accepted into any of the best journals in theoretical computer science.  Before it has been peer reviewed, people will generally assume it is incorrect, and most likely no one will find it worth their time to read it for you to check the details carefully.  Also, it is not about 3-regular graphs, so your answer seems more like naive self-promotion than an answer to the posted question.  
> **username_3**: @username_2. Thank you for your comment. I should say that I submitted it. But, due to critical points of view about this problem, I liked to contact with expert researchers (for presentation of my idea/for collaburation with them to improve the idea).  
> **username_2**: Well, if you must, maybe make a separate post with your own question, rather than piggybacking on a question that is only tangentially related...  Your question seems to be "*is there an error in my paper"*?  

---

