  DNA computing, a nontraditional computing mechanism, provides a feasible and
effective method for solving NP-hard problems because of the vast parallelism
and high-density storage of DNA molecules. Although DNA computing has been
exploited to solve various intractable computational problems, such as the
Hamiltonian path problem, SAT problem, and graph coloring problem, there has
been little discussion of designing universal DNA computing-based models, which
can solve a class of problems. In this paper, by leveraging the dynamic and
enzyme-free properties of DNA strand displacement, we propose a universal model
named DCMSubset for solving subset problems in graph theory. The model aims to
find a minimum (or maximum) set satisfying given constraints. For each element
x involved in a given problem, DCMSubset uses an exclusive single-stranded DNA
molecule to model x as well as a specific DNA complex to model the relationship
between x and other elements. Based on the proposed model, we conducted
simulation and biochemical experiments on three kinds of subset problems, a
minimum dominating set, maximum independent set, and minimum vertex cover. We
observed that DCMSubset can also be used to solve the graph coloring problem.
Moreover, we extended DCMSubset to a model for solving the SAT problem. The
results of experiments showed the feasibility and university of the proposed
method. Our results highlighted the potential for DNA strand displacement to
act as a computation tool to solve NP-hard problems.
