An Improved DNA Solution to the Vertex Cover Problem

For an undirected graph G=(V,E) and a positive integer k, kles|V|, the vertex cover problem is to find a vertex subset V´ of size k that satisfies: Each edge in E is incident to at least one vertex in V´. We give a DNA solution to the vertex cover problem through designing an improved polynomial transformation from the vertex cover problem to the Hamiltonian circle problem. It first constructs the improved cover subgraph of each edge in G, which has 4 vertices and 4 edges instead of 12 vertices and 14 edges in the previous method. For each vertex, the improved cover subgraphs of the edges incident to it are linked together to form one subpath; for each selection vertex, the start and end points of each subpath are linked to it. The obtained graph G´ has a Hamiltonian circle if and only if G has a vertex cover of size k. Thus, based on Adleman´s experiment of solving the Hamiltonian path problem, we give a DNA solution to the vertex cover problem.