A Volume Molecular Solution for the Maximum Matching Problem on DNA-Based Computing

DNA computing makes use of biomolecules as information storage materials and biological laboratory experiments as information processing operators. At present, DNA computing has been employed to many different decisions or combinatorial optimization problems and it has led to an important breakthrough in computing. The power of parallel, high density computation by molecules in solution also allows DNA computer to solve hard computational problems such as NP-complete problems. The maximum matching problem is a famous NP-complete problem. For the objective to decrease the solution volume of the DNA computing algorithm for the maximum matching problem, the pruning strategy is introduced into the DNA supercomputing and a DNA computing algorithm is proposed. The new algorithm consists of a graph composer, a resolvent generator, a parallel matching generator and a maximum matching searcher. Compared with the existing molecular algorithms for maximum matching problem, the DNA strands of maximum number required is reduced from O(2\+m) to O(1.618\+m) on the condition of not varying the time complexity. Therefore, the cardinal number of the exact cover problem that can be theoretically resolved in a test tube may be enlarged from 60 to 86, thus the proposed algorithm is an improved result over the past researches.This algorithm is space-efficient and error-tolerant compared with conventional brute-force searching, and thus it can be scaled-up to solve large and hard maximum clique problems.