A (1.999999)-approximation ratio for vertex cover problem (2025)

Majid Zohrehbandian
Department of Mathematics, Karaj Branch,
Islamic Azad University, Karaj, Iran.
zohrebandian@yahoo.com

Abstract

The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied. While a 2-approximation can be trivially obtained for it, researchers have not been able to approximate it better than 2-o(1).In this paper, by introducing a new semidefinite programming formulation that satisfies new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the correctness of the unique games conjecture.

Keywords Combinatorial Optimization $\cdot$ Vertex Cover Problem $\cdot$ Unique Games Conjecture $\cdot$ Complexity Theory

1 Introduction

In complexity theory, the abbreviation NP refers to "nondeterministic polynomial", where a problem is in NP if we can quickly(in polynomial time) test whether a solution is correct. P and NP-complete problems are subsets of NP problems.We can solve P problems in polynomial time while determining whether or not it is possible to solve NP-complete problems quickly(called the P vs NP problem) is one of the principal unsolved problems in Mathematics and Computer science.

Here, we consider the vertex cover problem (VCP) which is a famous NP-complete problem. It cannot be approximated within a factor of 1.36 [1],unless P=NP, while a 2-approximation factor for it can be trivially obtained by taking all the vertices of a maximal matchingin the graph. However, improving this simple 2-approximation algorithm is a hard task [2, 3].

In this paper, based on a lower bound on the objective value of VCP feasible solutions,we introduce a (2- $\varepsilon$ )-approximation ratio, where the value of $\varepsilon$ is not constant.Then, we introduce a new semidefinite programming (SDP) formulation and fix the $\varepsilon$ value equal to $\varepsilon$ =0.000001,to produce a 1.999999-approximation ratio on arbitrary graphs.

The rest of the paper is structured as follows.Section 2 is about the vertex cover problem and introduces new properties about it.In section 3, using a new SDP model whose solution satisfies the properties, we propose a solution algorithm for VCPwith a performance ratio of 1.999999 on arbitrary graphs.Finally, Section 4 concludes the paper.

2 Performance ratio based on VCP feasible solutions

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such thateach edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex coveris a typical example of an NP-complete optimization problem. In this section,we calculate the performance ratios of VCP feasible solutions to produce an approximation ratio of 2- $\varepsilon$ ,where the value of $\varepsilon$ is not constant and it depends on the VCP objective value.Then, in the next section, we will fix the value of $\varepsilon$ equal to $\varepsilon$ =0.000001, to produce a 1.999999-approximation ratiofor the vertex cover problem.

Let $G=(V,E)$ be an undirected graph on vertex set $V$ and edge set $E$ , where $\mid$ V $\mid=n$ .Throughout this paper, $z^{*}(G)$ is the optimal value for the vertex cover problem on $G$ , andVCP feasible solutions have been introduced by a vertex partitioning $V=V_{1}\cup V_{0}$ with an objective value $\mid V_{1}\mid$ .

The integer linear programming (ILP) model for VCP is as follows; i.e. $z1^{*}=z^{*}(G)$ .

(1)\ min_{s.t.}\ z1=\sum_{i\in V}x_{i}

x_{i}+x_{j}\geq 1\ \ \ ij\in E

x_{i}\in\{0,+1\}\ \ \ i\in V

Lemma 1. [4] Let $x^{*}$ be an extreme optimal solution to the linear programming (LP) relaxation of the model (1).Then $x_{j}^{*}\in\{0,0.5,1\}$ for $j\in V$ . If we define $V^{0}=\{j\in V\mid x_{j}^{*}=0\}$ , $V^{0.5}=\{j\in V\mid x_{j}^{*}=0.5\}$ and $V^{1}=\{j\in V\mid x_{j}^{*}=1\}$ , then there exists a VCP optimal solution which includes all of the vertices $V^{1}$ , and it is a subset of $V^{0.5}\cup V^{1}$ .

Theorem 1. Let $x^{*}$ be an extreme optimal solution to the LP relaxation of the model (1), $V^{0}=\{j\in V\mid x_{j}^{*}=0\}$ , $V^{0.5}=\{j\in V\mid x_{j}^{*}=0.5\}$ , $V^{1}=\{j\in V\mid x_{j}^{*}=1\}$ , and $G_{0.5}$ be the induced graph on the vertices $V^{0.5}$ . If we can introduce a vertex cover feasible partitioning $V^{0.5}=V_{1}^{0.5}\cup V_{0}^{0.5}$ with an approximation ratio of $1\leq\rho<2$ , for the VCP on $G_{0.5}$ ,then the vertex cover feasible partitioning $V=(V_{1}\cup V_{0})=(V_{1}^{0.5}\cup V^{1})\cup(V_{0}^{0.5}\cup V^{0})$ ,has an approximation ratio of $1\leq\rho<2$ , for the VCP on $G$ .
Proof. Based on the approximation ratio of $\frac{\mid V_{1}^{0.5}\mid}{z^{*}(G_{0.5})}\leq\rho$ , we have,

\mid V_{1}^{0.5}\mid+\mid V^{1}\mid\leq\rho z^{*}(G_{0.5})+\rho\mid V^{1}\mid

Therefore, $\frac{\mid V_{1}\mid}{z^{*}(G)}=\frac{\mid V_{1}^{0.5}\mid+\mid V^{1}\mid}{z^{%*}(G_{0.5})+\mid V^{1}\mid}\leq\rho\ \diamond$

Based on the Theorem (1), it is sufficient to produce an approximation ratio of $1\leq\rho<2$ , on $G_{0.5}$ .Then, let’s focus on $G_{0.5}$ and assume that for the optimal solution of the LP relaxation of the model (1), we have $V^{0}=V^{1}=\{\}$ , $V^{0.5}=V$ ; i.e. $G=G_{0.5}$ .

We know that we can efficiently solve the following SDP formulation,as a relaxation of the VCP model (1).

(2)\ min_{s.t.}\ z2=\sum_{i\in V}X_{oi}

X_{oi}+X_{oj}\geq 1\ \ \ ij\in E

0\leq X_{oi}\leq+1\ \ \ i\in V

X\succeq 0

This model can be written as follows,

(3)\ min_{s.t.}\ z3=\sum_{i\in V}X_{oi}

X_{oi}+X_{oj}-X_{ij}=1\ \ \ ij\in E

X_{ii}=1,\ \ \ 0\leq X_{ij}\leq+1\ \ \ i,j\in V\cup\{o\}

X\succeq 0

Moreover, by introducing the normal vectors $v_{o},v_{1},...,v_{n}$ , the SDP model (3) can be written as follows,where $v_{i}v_{j}=X_{ij}$ , $V_{1}=\{i\in V\mid v_{i}=v_{o}\}$ is a feasible vertex cover,and $V_{o}=V-V_{1}$ is the set of perpendicular vectors to $v_{o}$ .

(4)\ min_{s.t.}\ z4=\sum_{i\in V}v_{o}v_{i}

v_{o}v_{i}+v_{o}v_{j}-v_{i}v_{j}=1\ \ \ ij\in E

v_{i}v_{i}=1,\ \ \ 0\leq v_{i}v_{j}\leq+1\ \ \ i,j\in V\cup\{o\}

Theorem 2. Let $\frac{n}{2}+\frac{n}{k}$ be a lower bound on VCP optimal value ( $z^{*}(G)\geq\frac{n}{2}+\frac{n}{k}=\frac{(k+2)n}{2k}$ ). Then, for all vertex cover feasible partitioning $V=V_{1}\cup V_{0}$ , we have the approximation ratio $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq\frac{2k}{k+2}<2$ .
Proof. If $z^{*}(G)\geq\frac{(k+2)n}{2k}$ , then $\frac{n}{z^{*}(G)}\leq\frac{2k}{k+2}$ .Therefore,

\frac{\mid V_{1}\mid}{z^{*}(G)}\leq\frac{n}{z^{*}(G)}\leq\frac{2k}{k+2}<2

and this completes the Proof $\diamond$

Theorem 3. Let $z^{*}(G)\geq\frac{n}{2}$ , and we have a VCP feasible partitioning $V=V_{1}\cup V_{0}$ ,where $\mid V_{1}\mid\leq\frac{kn}{k+1}$ and $\mid V_{0}\mid\geq\frac{n}{k+1}$ (or $\mid V_{1}\mid\leq k\mid V_{0}\mid$ ). Then, based on such a solution, we have an approximation ratio $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq\frac{2k}{k+1}<2$ .
Proof. If $\mid V_{1}\mid\leq\frac{kn}{k+1}$ , then $n\geq\frac{k+1}{k}\mid V_{1}\mid$ .Hence, $z^{*}(G)\geq\frac{n}{2}\geq\frac{k+1}{2k}\mid V_{1}\mid$ and $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq\frac{2k}{k+1}<2\ \diamond$

3 A (1.999999)-approximation algorithm on arbitrary graphs

In section 2, we introduced a (2- $\varepsilon$ )-approximation ratio for VCP,where $\varepsilon$ value was not constant. In this section, we fix the value of $\varepsilon$ equal to $\varepsilon$ =0.000001to produce a 1.999999-approximation ratio on arbitrary graphs. To do this,we introduce the following property on a solution of the SDP model (4).

Property 1. For some vertex cover problems, both of the following conditions occur after solving the SDP model (4).

a) For less than 0.000001n of vertices $j\in V$ and corresponding vectors we have $v_{o}^{*}v_{j}^{*}<0.5$ .

b) For less than 0.01n of vertices $j\in V$ and corresponding vectors we have $v_{o}^{*}v_{j}^{*}>0.5004$ .

Theorem 4. If $z^{*}(G)\geq\frac{n}{2}$ and the optimal solution of the SDP model (4) does not meet the Property (1),then we can produce a VCP solution with a performance ratio of 1.999999.
Proof. If the optimal solution of the SDP model (4) does not meet the Property (1.a),then we can introduce $V_{0}=\{j\in V\mid v_{o}^{*}v_{j}^{*}<0.5\}$ and $V_{1}=V-V_{0}$ , to have a VCP feasible solutionwith $\mid V_{0}\mid\geq 0.000001n$ and $\mid V_{1}\mid\leq 0.999999n\leq 999999\mid V_{0}\mid$ .Therefore, for such a solution and based on the Theorem (3), we have an approximation ratio of $\frac{\mid V_{1}\mid}{z^{*}(G)}<\frac{2(999999)}{999999+1}=1.999998<1.999999$ .

Otherwise, if the optimal solution of the SDP model (4) meets the Property (1.a) but does not meet the Property (1.b), then there exists the following lower bound on $z^{*}(G)$ value.

z^{*}(G)\geq z4^{*}\geq(0)(0.000001n)_{\{s.t.\ v_{o}^{*}v_{j}^{*}<0.5\}}

+(0.5)(0.989999n)_{\{s.t.\ v_{o}^{*}v_{j}^{*}\geq 0.5\}}+(0.5004)(0.01n)_{\{s.%t.\ v_{o}^{*}v_{j}^{*}>0.5004\}}

=\frac{n}{2}+0.0000035n

Note that, the Property (1.a) is met and we have less than 0.000001n of vertices $j\in V$ with $v_{o}^{*}v_{j}^{*}<0.5$ .The Property (1.b) is not met and we have more than 0.01n of vertices $j\in V$ with $v_{o}^{*}v_{j}^{*}>0.5004$ .Therefore, in the above inequality, the first summation is the lower bound on the vertices $j\in V$ with $v_{o}^{*}v_{j}^{*}<0.5$ ,and the third summation is the lower bound on only 0.01n of the vertices $j\in V$ with $v_{o}^{*}v_{j}^{*}>0.5004$ . In other words,beyond the 0.01n of such vertices are considered in the second summation.Moreover, the second summation is the lower bound on the other vertices (the vertices $j\in V$ with $0.5\leq v_{o}^{*}v_{j}^{*}\leq 0.5004$ or the vertices $j\in V$ with $v_{o}^{*}v_{j}^{*}>0.5004$ and beyond the 0.01n of such vertices considered in the third summation).

Therefore, based on the above lower bound on $z^{*}(G)$ value and based on the Theorem (2), for all VCP feasible solutions $V=V_{1}\cup V_{0}$ ,we have the approximation ratio $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq\frac{2(\frac{1}{0.0000035})}{\frac{1}{0.00%00035}+2}<1.999999\ \diamond$

Definition 1. Let $\varepsilon$ =0.0004 and $V_{\varepsilon}=\{j\in V\mid 0.5\leq v_{o}^{*}v_{j}^{*}\leq 0.5+\varepsilon\}$ .

After solving the SDP model (4) on problems with $z^{*}(G)\geq\frac{n}{2}$ ,
i) If the solution of the SDP model (4) does not meet the Property (1), then we have a performance ratio of 1.999999,
ii) Otherwise (The solution of the SDP model (4) meets the Property (1)), for more than 0.989999n of vertices $j\in V$ ,we have $0.5\leq v_{o}^{*}v_{j}^{*}\leq 0.5+\varepsilon$ ; i.e. $\mid V_{\varepsilon}\mid\geq 0.989999n$ . Moreover, for each edge $ij$ in $E_{\varepsilon}=\{ij\in E\mid i,j\in V_{\varepsilon}\}$ ,we have $v_{o}^{*}v_{i}^{*}+v_{o}^{*}v_{j}^{*}-v_{i}^{*}v_{j}^{*}=1$ (That is $0\leq v_{i}^{*}v_{j}^{*}\leq 2\varepsilon=0.0008$ ),and the corresponding vectors of each edge in $E_{\varepsilon}$ are almost perpendicular to each other.

Therefore, to produce a VCP performance ratio of 1.999999 for problems with $z^{*}(G)\geq\frac{n}{2}$ ,we need a solution for the SDP model (4) that does not meet the Property (1). To do this, we introduce a new SDP model.

Let $G2=(V_{new},E_{new})$ be a new graph, where we add two adjacent vertices $a$ and $b$ to the graph $G$ ,and connect all vertices of $G$ to them.Then, based on the SDP model (4), and by introducing the normal vectors $v_{o},v_{1},...,v_{n},v_{a},v_{b}$ , we introduce a new SDP model as follows, where $V_{1new}=V_{1}=\{i\in V_{new}\mid v_{i}=v_{o}\}$ corresponds to a feasible vertex cover on graph $G$ , and $V_{0new}=V_{0}=V-V_{1}$ corresponds to perpendicular vectors to $v_{o}$ .

(5)\ min_{s.t.}\ z5=\sum_{i\in V}v_{o}v_{i}

SDP\ (4)\ constraints\ on\ G

v_{o}v_{i}+v_{o}v_{j}-v_{i}v_{j}=1\ \ \ i\in V,\ j\in\{a,b\}

-0.5\leq v_{i}v_{j}\leq+0.5\ \ \ i\in V,\ j\in\{a,b\}

v_{i}v_{i}=1,\ \ \ v_{o}v_{i}=\ +0.5\ \ \ i\in\{a,b\}

v_{a}v_{b}=\ 0

Lemma 2. Due to the additional constraints, we have $z5^{*}\geq z4^{*}$ . Moreover, to produce a feasible solutionfor the SDP model (5) on $G2$ , we can add suitable vectors $v_{a}$ and $v_{b}$ to each VCP feasible partitioning $V=V_{1}\cup V_{0}$ on $G$ , where $v_{i}v_{j}=\ +0.5$ for $i\in V_{1},\ j\in\{a,b\}$ , and $v_{i}v_{j}=\ -0.5$ for $i\in V_{0},\ j\in\{a,b\}$ (For example, for $v_{o}=v_{i}=[0.5,0.5,0.5,0.5]^{t}\in V_{1}$ and $v_{i}=[-0.5,-0.5,0.5,0.5]^{t}\in V_{0}$ , we can introduce $v_{a}=e_{1}=[1,0,0,0]^{t}$ , and $v_{b}=e_{2}=[0,1,0,0]^{t}$ ). Therefore, $z5^{*}\leq z^{*}(G)$ .

We are going to prove that by solving the SDP model (5) on problems with $z^{*}(G)\geq\frac{n}{2}$ ,it is impossible to produce a solution that meets the Property (1) on $G$ , unless the induced graph on $V_{\varepsilon}$ is bipartite.

Theorem 5. For four normalized vectors $v_{1},v_{2},v_{3},v_{4}$ which are perpendicular to each other,there exists exactly one normalized vector $v$ with $vv_{i}=0.5\ (i=1,2,3,4)$ . Such a vector $v$ satisfies the equation $v=0.5(v_{1}+v_{2}+v_{3}+v_{4})$ .
Proof.

Due to $v_{1}v_{2}=0$ , we have $\mid v_{1}+v_{2}\mid=\sqrt{\mid v_{1}\mid^{2}+\mid v_{2}\mid^{2}}=\sqrt{2}$ .

Due to $v_{3}v_{4}=0$ , we have $\mid v_{3}+v_{4}\mid=\sqrt{\mid v_{3}\mid^{2}+\mid v_{4}\mid^{2}}=\sqrt{2}$ .

Due to $(v_{1}+v_{2})(v_{3}+v_{4})=0$ , we have $\mid v_{1}+v_{2}+v_{3}+v_{4}\mid=2$ .

Moreover, we have $(v_{1}+v_{2}+v_{3}+v_{4})v=2$ . Hence, $\mid v_{1}+v_{2}+v_{3}+v_{4}\mid\mid v\mid cos(\theta)=2$ andthis concludes that $\theta=0$ and $v=0.5(v_{1}+v_{2}+v_{3}+v_{4})\ \diamond$

proposition 1. For four normalized vectors $v_{1},v_{2},v_{3},v_{4}$ which are almost perpendicular to each other, their halved sum as $w=0.5(v_{1}+v_{2}+v_{3}+v_{4})$ , anda normalized vector $v$ with $0.5\leq vv_{i}\leq 0.5+\varepsilon\ (i=1,2,3,4)$ , the vector $v$ is almost equal to $w$ . In other words,there exists a vector $r$ with $w+r=v$ , where $-\varepsilon\leq\mid w\mid-\mid v\mid\leq\varepsilon,\ \mid r\mid\leq\varepsilon$ , and $cos(w,v)\geq 1-\varepsilon$ .

Theorem 6. Let $\theta(v,w)=cos^{-1}(\frac{v.w}{\mid v\mid\mid w\mid})$ , and a vector $U$ with $\mid U\mid=\sqrt{2}$ , and $2n+1$ normalized vectors $v_{1},\dots,v_{2n+1}$ , where $Uv_{i}=1\ (i=1,\dots,2n+1)$ , and $0\leq v_{i}v_{i+1}\leq\varepsilon\ (i=1,\dots,2n)$ , and $v_{i}+v_{i+1}\ (i=1,\dots,2n)$ is almost equal to $U$ (i.e. $-\varepsilon\leq\mid U\mid-\mid v_{i}+v_{i+1}\mid\leq\varepsilon$ , and $cos(U,v_{i}+v_{i+1})\geq 1-\varepsilon$ ). Then, we have $\theta(U,v_{1}+\dots+v_{2n})\ <\theta(U,v_{1}+\dots+v_{2n+1})$ .
Proof. We give proof by induction on n. For $3$ normalized vectors $v_{1},v_{2},v_{3}$ , we have $v_{1}+v_{2}$ is almost equal to $U$ and $\theta(U,v_{3})=45^{o}$ , and this concludes that $cos(U,U+v_{3})=\frac{3\sqrt{10}}{10}=0.94868$ and $\theta(U,v_{1}+v_{2})\ <\theta(U,v_{1}+v_{2}+v_{3})$ . Therefore, the Theorem is true for $n=1$ . Supposethat it is true for $n-1$ , and we wantto prove it for $n$ .

Let $v_{1},\dots,v_{2n+1}$ be $2n+1$ normalized vectors that satisfy the properties of the theorem. Our inductive hypothesis implies that $\theta(U,v_{3}+\dots+v_{2n})\ <\theta(U,v_{3}+\dots+v_{2n+1})$ . Therefore, by addition of the vector $v_{1}+v_{2}$ we have $\theta(U,v_{1}+v_{2}+v_{3}+\dots+v_{2n})\ <\theta(U,v_{1}+v_{2}+v_{3}+\dots+v_%{2n+1})$ and this completes the proof $\diamond$

Theorem 7. Based on the solution of the SDP model (5), and by introducing $U=2v_{o}^{*}-v_{a}^{*}-v_{b}^{*}$ , we have

\mid U\mid=\sqrt{2},\ \ \ \ \ \ \ \forall j\in V_{\varepsilon}:\ Uv_{j}^{*}=1

Proof.

\mid U\mid=\sqrt{UU}=\sqrt{4-1-1-1+1+0-1+0+1}=\sqrt{2}

Moreover, for each vertex $j$ in $V_{\varepsilon}$ , we have

v_{o}^{*}v_{c}^{*}+v_{o}^{*}v_{j}^{*}-v_{c}^{*}v_{j}^{*}=1\ \ \ c\in\{a,b\},\ %\ j\in V_{\varepsilon}

Therefore, we obtain

v_{c}^{*}v_{j}^{*}=-0.5+v_{o}^{*}v_{j}^{*}\ \ \ c\in\{a,b\},\ \ j\in V_{\varepsilon}

which concludes that $Uv_{j}^{*}=2v_{o}^{*}v_{j}^{*}-v_{a}^{*}v_{j}^{*}-v_{b}^{*}v_{j}^{*}=2v_{o}^{*%}v_{j}^{*}+0.5-v_{o}^{*}v_{j}^{*}+0.5-v_{o}^{*}v_{j}^{*}=1$ , and the angle between two vectors $U$ and $v_{j}$ is $45$ degrees for $j\in V_{\varepsilon}\ \diamond$

Now we can prove our main result.

Theorem 8. By solving the SDP model (5) on $G2$ , it is impossible to have an optimal solution that meets the Property (1)on $G$ , unless the induced graph on $V_{\varepsilon}$ is bipartite.
Proof. Suppose that the optimal solution of the SDP model (5) meets the Property (1) on $G$ .Therefore, for each edge $ij$ in $E_{\varepsilon}$ we have four normalized vectors $v_{i}^{*},v_{j}^{*},v_{a}^{*},v_{b}^{*}$ which are almost perpendicular to each other,and a normalized vector $v_{o}^{*}$ with $0.5\leq v_{o}^{*}v_{c}\leq 0.5+\varepsilon$ $(c=i,j,a,b)$ which is almost equal to $0.5(v_{i}^{*}+v_{j}^{*}+v_{a}^{*}+v_{b}^{*})$ . In other words, there exists a vector $r_{i,j}$ with $v_{i}^{*}+v_{j}^{*}+r_{i,j}=U$ , where $-\varepsilon\leq\mid v_{i}^{*}+v_{j}^{*}\mid-\mid U\mid\leq\varepsilon,\ \mid r%_{i,j}\mid\leq\varepsilon$ , and $cos(U,v_{i}^{*}+v_{j}^{*})\geq 1-\varepsilon$ .

Now, suppose that we have an odd cycle on $2t+1$ vertices in $G_{\varepsilon}=(V_{\varepsilon},E_{\varepsilon})$ . By addition of the vectors in this cycle and introducing $W=(v_{1}+v_{2})+(v_{2}+v_{3})+...+$ $(v_{2t}+v_{2t+1})+(v_{2t+1}+v_{1})$ , we have

U.W=\ 2(2t+1)=\mid U\mid\mid W\mid cos(U,W)

By introducing $W^{\prime}=v_{1}+v_{2}+v_{3}+v_{4}+...+v_{2t-1}+v_{2t}+v_{2t+1}=\ 0.5W$ , the above summation can be written as follows,

U.W=2U.W^{\prime}=2\mid U\mid\mid W^{\prime}\mid cos(U,W^{\prime})=\ 2(2t+1)

Where

\frac{(t+0.5)\sqrt{2}}{1}\leq\mid W^{\prime}\mid=\frac{(t+0.5)\sqrt{2}}{cos(U,%W^{\prime})}

By introducing $W_{i}=W^{\prime}-v_{i}$ , for $i=1,...,2t+1$ , we have

U.W_{i}=\ 2t=\mid U\mid\mid W_{i}\mid cos(U,W_{i})

Where

\frac{t\sqrt{2}}{1}\leq\mid W_{i}\mid=\frac{t\sqrt{2}}{cos(U,W_{i})}

By addition of the $W_{i}$ vectors in this cycle, we have

\mid\sum_{i=1}^{2t+1}W_{i}\mid=\mid(2t+1)W^{\prime}-\sum_{i=1}^{2t+1}v_{i}\mid%=\mid 2tW^{\prime}\mid=\frac{2t(t+0.5)\sqrt{2}}{cos(U,W^{\prime})}=\frac{t(2t+%1)\sqrt{2}}{cos(U,W^{\prime})}

Moreover, we have

\mid\sum_{i=1}^{2t+1}W_{i}\mid\leq\sum_{i=1}^{2t+1}\mid W_{i}\mid\leq\frac{(2t%+1)t\sqrt{2}}{min\{cos(U,W_{i}):\ i=1,\dots,2t+1\}}

Therefore

\exists j:\ cos(U,W_{j})\leq cos(U,W^{\prime}),\ \ \ \theta(U,W_{j})\geq\theta%(U,W^{\prime})

Hence, there are $2t+1$ normalized vectors $v_{j+1},\dots,v_{2t+1},v_{1},\dots,v_{j}$ , which satisfy the conditions of the Theorem (6), but we have $\theta(U,v_{j+1}+\dots+v_{2t+1}+v_{1}+\dots+v_{j-1})\ \geq\theta(U,v_{j+1}+%\dots+v_{2t+1}+v_{1}+\dots+v_{j-1}+v_{j})$ , which is a contradiction.

Therefore, there is not any odd cycle in $G_{\varepsilon}$ , and, if the optimal solution of the SDP model (6) on $G2$ meets the Property (1) on $G$ , then the subgraph $G_{\varepsilon}$ is bipartite $\ \diamond$

proposition 2. To produce a performance ratio of 1.999999 for problems with $z_{VCP}^{*}\geq\frac{n}{2}$ ,we should solve the SDP model (5) on $G2$ . Then, if the solution does not meet the Property (1),we have a performance ratio of 1.999999. Otherwise, we can solve the VCP problem on the bipartite graph $G_{\varepsilon}$ ,where $\mid V_{\varepsilon}\mid\geq 0.989999n$ , to produce a performance ratio of 1.999999.

Moreover, based on the Theorem (1) and the proposition (2), to produce a performance ratio of 1.999999 for problems with $z_{VCP}^{*}<\frac{n}{2}$ , it is sufficient to produce an extreme optimal solution for the LP relaxation of the model (1), to introduce $G2$ based on $G_{0.5}$ .

Theorem 9. The Optimal solution of the following LP model corresponds to an extreme optimal solution of the LP relaxation of the model (1).

(6)\ min_{s.t.}z6=\sum_{i=1}^{n}(0.1)^{i}x_{i}

x_{i}+x_{j}\geq 1\ \ \ ij\in E

\sum_{i\in V}x_{i}=z^{*}_{LP\ relaxation\ of\ the\ model\ (1)}

0\leq x_{i}\leq+1\ \ \ i\in V

Proof. The feasible region of the model (6) is an optimal face of the feasible region of the LP relaxation of the model (1), andbased on the priority weights of the decision variables,its optimal solution corresponds to the solution of the following algorithm.
Step 0. Let k=1 and $z^{*}$ be the optimal value of the LP relaxation of the model (1).
Step k. Solve the following LP model.

(7)\ min_{s.t.}z(k)=x_{k}

x_{i}+x_{j}\geq 1\ \ \ ij\in E

\sum_{i\in V}x_{i}=z^{*}

x_{i}=x_{i}^{*}=z(k)^{*}\ \ \ i=1,\cdots,k-1

0\leq x_{i}\leq+1\ \ \ i\in V

Let k=k+1. If $k<n$ repeat this step, otherwise, the solution $x^{*}$ is an extreme optimal solution of the LP relaxation of the model (1) $\ \diamond$

Therefore, our algorithm to produce an approximation ratio of 1.999999, for arbitrary vertex cover problems, is as follows:

Mahdis Algorithm (To produce a vertex cover solution on graph G with a ratio factor $\rho=1.999999$ )
Step 1. Let $V^{1}=V^{0}=\{\}$ and solve the LP relaxation of the model (1) on $G$ .
Step 2. If $z^{*}_{LP\ relaxation\ of\ the\ model\ (1)}<\frac{n}{2}$ , then solve the model (6)to produce an extreme optimal solution of the LP relaxation of the model (1), and based on the solution ( $x_{j}^{*}\in\{0,0.5,1\}\ \ j\in V$ ),introduce $V^{0}=\{j\in V\mid x_{j}^{*}=0\}$ , $V^{0.5}=\{j\in V\mid x_{j}^{*}=0.5\}$ , $V^{1}=\{j\in V\mid x_{j}^{*}=1\}$ , and let $G=G_{0.5}$ as the induced graph on the vertex set $V^{0.5}$ .
Step 3. Produce $G2$ based on $G$ and solve the SDP (5) model.
Step 4. If $\mid\{j\in V\mid v_{o}^{*}v_{j}^{*}<0.5\}\mid>0.000001n$ , then produce a suitable solution $V_{1}\cup V_{0}$ ,correspondingly, where $V_{0}=\{j\in V\mid v_{o}^{*}v_{j}^{*}<0.5\}$ and $V_{1}=V-V_{0}$ and go to Step 7.Hence, the solution does not meet the Property (1.a) and we have $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq 1.999999$ . Otherwise, go to Step 5.
Step 5. If $\mid\{j\in V\mid v_{o}^{*}v_{j}^{*}>0.5004\}\mid>0.01n$ , then it is sufficient to produce an arbitraryVCP feasible solution $V=V_{1}\cup V_{0}$ to have $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq 1.999999$ and go to Step 7. Otherwise, go to Step 6.
Step 6. The solution meets the Property (1) and based on the Theorem (7), graph $G_{\varepsilon}$ is bipartite,and $\mid V_{\varepsilon}\mid\geq 0.989999n$ . Therefore, solve the VCP problem on bipartite subgraph $G_{\varepsilon}$ and add all vertices of $V-V_{\varepsilon}$ to the solution (That is $V_{1}=V_{1}\cup(V-V_{\varepsilon})$ ),to produce a feasible solution $V_{1}\cup V_{0}$ for which we have $\frac{\mid V_{1}\mid}{z^{*}(G)}\leq 1.999999$ . Then, go to Step 7.
Step 7. The partitioning $(V_{1}\cup V^{1})\cup(V_{0}\cup V^{0})$ produces a VCP feasible solution on the original graph $G$ with an approximation ratio factor $\rho=1.999999$ .

proposition 3. Based on the proposed 1.999999-approximation algorithm for the vertex cover problem, the unique games conjecture is not true.

4 Conclusions

One of the open problems about the vertex cover problem is the possibility of introducing an approximation algorithm within any constant factor better than 2. Here, we proposed a new algorithm to produce a 1.999999-approximation ratio for the vertex cover problem on arbitrary graphs, and this led to the conclusion that the unique games conjecture is not true.

Acknowledgment. I would like to sincerely thank Dr. Flavia Bonomo for her useful comments and her endorsement for publishing in arXiv.

Competing Interest and Data Availability
The authors have no relevant financial or non-financial interests to declare relevant to this article’s content. Data sharing does not apply to this article as no data sets were generated or analyzed during the current study.

References
1) Dinur I., Safra S. (2005) On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162, 439-485.
2) Khot S. (2002) On the power of unique 2-Prover 1-Round games. Proceeding of 34th ACM Symposium on Theory of Computing, STOC.
3) Khot S., Regev O. (2008) Vertex cover might be hard to approximate to within $2-\varepsilon$ . Journal of Computer and System Sciences, 74, 335-349.
4) Nemhauser G.L., Trotter L.E. (1975) Vertex packing: Structural properties and algorithms. Mathematical Programming, 8, 232-248.