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.
3
-
1$\begingroup$ 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). $\endgroup$– Yixin CaoCommented Apr 6 at 8:25
-
$\begingroup$ 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$. $\endgroup$– Neal YoungCommented Apr 14 at 0:44
-
$\begingroup$ @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... $\endgroup$– Yixin CaoCommented Apr 15 at 9:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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)!
-
$\begingroup$ 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. $\endgroup$ Commented Apr 14 at 0:28
-
$\begingroup$ @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). $\endgroup$ Commented Apr 14 at 8:43
-
$\begingroup$ 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"? $\endgroup$ Commented Apr 14 at 21:40