2007/12/20 by Qiaoming Han, Han, Qiaoming, Abraham P. Punnen +3
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2 #FOS: Computer and information sciences #G.1.6 #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.0712.3335
openalex publication_date 2007/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 S1 on an arbitrary graph such that |S1|≤ 3/2 |S^*|+ξ where S^* is an optimal vertex cover and ξ is an error bound identified by the algorithm. We obtained ξ= 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 ξ\not= 0.