Solving the Maximum Independent Set Problem based on Molecule Parallel Supercomputing

The maximum independent set Problem is to find a biggest vertex independent set in a given undirected graph. It is a vitally important NP problem in graph theory and applied mathematics, having numerous real life applications. It can be difficultly solved by the electronic computer in exponential level time. Simultaneity in previous studies DNA molecular computation usually be used to solve NP-complete continuous path search problems (for example HPP, traveling salesman problem), rarely for NP problems with discrete vertex or path solutions result, such as the maximum independent set problem, graph coloring problem and so on. In this paper, we present a new algorithm for solving the maximum independent set problem with DNA molecular operations. For an undirected graph with n vertices, We reasonably design fixed length DNA strands representing the vertices and edges of graph, take appropriate steps and get the solutions of the problem in proper length range using O(n2) time. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation