A polynomial time $\frac{3}{2}$ -approximation algorithm for the vertex cover problem on a class of graphs

We develop a polynomial time 3/2-approximation algorithm to solve the vertex cover problem on a class of graphs satisfying a property called ``active edge hypothesis’'. The algorithm also guarantees an optimal solution on specially structured graphs. Further, we give an extended algorithm which guarantees a vertex cover $S_1$ on an arbitrary graph such that $\mathrm{\mid }{S}_1\mathrm{\mid }\le 3\mathrm{/}2\mathrm{\mid }{S}^{\ast }\mathrm{\mid }+\xi$ where $S^{\ast }$ is an optimal vertex cover and $\xi$ is an error bound identified by the algorithm. We obtained $\xi =0$ for all the test problems we have considered which include specially constructed instances that were expected to be hard. So far we could not construct a graph that gives $\xi ≠0$.