A 3SDP relaxation to solve vertex cover problem
Majid Zohrehbandian · viXra · 2020
Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied. It is known that it is hard to approximate to within any constant factor better than 2. In this paper, based on the addition of new constraints to the combination of 3 semidefinite programming (SDP) relaxations, we introduce a new stronger SDP relaxation for vertex cover problem which solve it exactly on general graphs. In this manner and by solving one of the NP-complete problems in polynomial time, we conclude that P=NP.