The vertex coloring problem is a well-known combinatorial problem that requires each vertex to be assigned a corresponding color so that the colors on adjacent vertices are different, and the total number of colors used is minimized. It is a famous NP-hard problem in graph theory. As of now, there is no effective algorithm to solve it. As a kind of intelligent computing algorithm, DNA computing has the advantages of high parallelism and high storage density, so it is widely used in solving classical combinatorial optimization problems. In this paper, we propose a new DNA algorithm that uses DNA molecular operations to solve the vertex coloring problem. For a simple n-vertex graph and k different kinds of color, we appropriately use DNA strands to indicate edges and vertices. Through basic biochemical reaction operations, the solution to the problem is obtained in the O (kn2) time complexity. Our proposed DNA algorithm is a new attempt and application for solving Nondeterministic Polynomial (NP) problem, and it provides clear evidence for the ability of DNA calculations to perform such difficult computational problems in the future.
FeynmanR.P., Mathematical formulation of the quantum theory of electromagnetic interaction, Physical Review80(3) (1950), 440–457.
2.
AdlemanL.M., Molecular computation of solution to combinatorial problems, Science266 (1994), 1021–1024.
3.
LiptonR.J., DNA solution of HARD computational problems, Science268 (1995), 542–545.
4.
KamioS., TakeharaA. and FujiwaraA., Procedures for computing the maximum with DNA strands, in: Humid R. Arabnia, Youngsong Mun (Eds.), Proceedings of the International Conference on DNA Based Computers, 2003.
5.
HugH. and SchulerR., DNA-based parallel computation of simple arithmetic, in: Proceedings of the 7th International Meeting on DNA Based Computers, (2001) 159–166.
6.
GuarnieriF., FlissM. and BancroftC., Making DNA add, Science273 (1996), 220–223.
7.
LiW.X., XiaoD.M. and HeL., DNA ternary addition, Applied Mathematics and Computation182 (2006), 977–986.
8.
XiaoD.M., LiW.X., YuJ., ZhangX.D., ZhangZ.Z. and HeL., Procedures for a dynamical system on {0, 1} n with DNA molecules, BioSystems84 (2006), 207–216.
9.
ChangW.L., Fast Parallel DNA-Based Algorithms for Molecular Computation: Quadratic Congruence and Factoring Integers, IEEE Transactions on NanoBioscience11(1) (2012), 62–69.
10.
ChangW.L., HuangS.C. and LinK.W., Fast parallel DNA-based algorithms for molecular computation: discrete logarithm, The Journal of Supercomputing56(2) (2011), 129–163.
11.
JiZ.W., WangZ.C., WuT.H. and HuangW., Solving the 0-1 knapsack problem based on a parallel intelligent molecular computing model system, Journal of Intelligent & Fuzzy Systems33(5) (2017), 2719–2726.
12.
WangX.L., BaoZ.M., HuJ.J., WangS. and ZhanA., Soling the SAT problem using a DNA computing algorithm based on ligase chain reaction, BioSystems91 (2008), 117–125.
13.
DengW., XuJ., SongY. and ZhaoH., Differential evolution algorithm with wavelet basis function and optimal mutation strategy for complex optimization problem, Applied Soft Computing (2020), 106724.
14.
WangZ.C., RenX.M., JiZ.W., HuangW. and WuT.H., A novel bio-heuristic computing algorithm to solve the capacitated vehicle routing problem based on Adleman-Lipton model, Biosystems184 (2019), 103997.
15.
DengW., LiuH., XuJ., ZhaoH. and SongY., An improved quantum-inspired differential evolution algorithm for deep belief network, IEEE Transactions on Instrumentation & Measurement69(10) (2020), 7319–7327.
16.
YamamuraM., HirotoY. and MatobaT., Solutions of shortest path problems by concentration control, Lecture Notes Computer Science2340 (2002), 231–240.
17.
SongZ.G., XuJ. and ZhenB., Mixed-coexistence of periodic orbits and chaotic attractors in an inertial neural system with a nonmonotonic activation function, Mathematical Biosciences and Engineering16 (2019), 6406–6425.
18.
PaunG., RozebergG. and SalomaaA., DNA Computing, Springer-Verlag, (1998).
19.
YaoS.W., DingL.W., SongZ.G. and XuJ.Q., Two bifurcation routes to multiple chaotic coexistence in an inertial two-neural system with time delay, Nonlinear Dynamics95 (2019), 1549–1563.
20.
OuyangQ., KaplanP.D., LiuS. and LibchaberA., DNA solution of the maximal clique problem, Science278 (1997), 446–449.
21.
ZhaoH.M., ZhengJ.J., DengW. and SongY.J., Semi-supervised broad learning system based on manifold regularization and broad network, IEEE Transactions on Circuits and Systems I- Regular Papers67(3) (2020), 983–994.
22.
WangZ.C., JiZ.W., WangX.M., WuT.H. and HuangW., A new parallel DNA algorithm to solve the task scheduling problem based on inspired computational model, Biosystems162 (2017), 59–65.
23.
DengA., WangZ., LiuH. and WuT., A bio-inspired algorithm for a classical water resources allocation problem based on Adleman-Lipton model, Desalination and Water Treatment185 (2020), 168–174.
24.
WangZ.C., HuangD.M., MengH.J., et al., A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation, Biosystems114(1) (2013), 1–7.
25.
GualandiS. and MalucelliF., A simple branching scheme for vertex coloring problems, Discrete Applied Mathematics160 (2012), 192–196.
26.
MalagutiE., MonaciM. and TothP., An exact approach for the Vertex Coloring Problem, Discrete Optimization8 (2011), 174–190.
MajidD., A New Solution for Maximal Clique Problem based Sticker Model, Biosystems95 (2009), 145–149.
29.
MokhtarN., DNA sequence design for DNA computation based on binary particle swarm optimization, International Journal of Innovative Computing, Information and Control8(5B) (2012), 3441–3450.
30.
GareyM.R. and JohnsonD.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.
31.
KarpR.M., Reducibility among combinatorial problems[M], Complexity of computer computations. Springer, Boston, MA, 1972:85–103.
32.
HertzA. and de WerraD., Using tabu search techniques for graph coloring, Computing39(4) (1987), 345–351.
33.
CaramiaM. and Dell’OlmoP., A Fast and Simple Local Search for Graph Coloring, Lecture Notes in Computer Science1668 (1999), 317–330.
34.
VoudourisC. and TsangE.P.K., Guided Local Search. In Handbook of Metaheuristics, edited by GloverF., 185–218. Norwell, MA: Kluwer Academic Publishers, 2003.
35.
CaramiaM. and Dell’OlmoP., Coloring graphs by iterated local search traversing feasible and infeasible solutions, Discrete Applied Mathematics156(2) (2008), 201–217.
36.
GalinierP., HertzA. and ZuffereyN., An adaptive memory algorithm for the k-coloring problem, Discrete Applied Mathematics156(2) (2008), 267–279.
37.
CaramiaM. and Dell’OlmoP., Embedding a novel objective function in a two-phased local search for robust vertex coloring, European Journal of Operational Research189(3) (2008), 1358–1380.
38.
WangZ.C., HuangD.M., TanJ., LiuT.G., TanJ. and LiL., A parallel algorithm for solving the n-queens problem based on inspired computational model, Biosystems131 (2015), 22–29.
39.
WangZ.C., ZhangY.M, ZhouW.H. and LiuH.F., Solving traveling salesman problem in the Adleman-Lipton model, Applied Mathematics and Computation219 (2012), 2267–2270.
40.
NarayananA., ZorbalasS., et al., DNA algorithms for computing shortest paths, in: J.R. Koza (Ed.), Proceedings of the Genetic Programming 1998, Morgan Kaufmann, (1998), 718–723.
41.
SchiermeyerI., Deciding 3-colourability in less than O(1.415n) steps[C], International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, Berlin, Heidelberg (1993), 177–188.
42.
BeigelR. and EppsteinD., 3-coloring in time O (1 . n), Journal of Algorithms54(2) (2005), 168–204.
43.
ChaiX., ChenY. and BroydeL., A novel chaos-based image encryption algorithm using DNA sequence operations, Optics and Lasers in Engineering88 (2017), 197–213.
44.
LiangX, ZhuW. and LvZ., Molecular Computing and Bioinformatics, Molecules24(13) (2019), 2358.
45.
XuJ., QiangX., ZhangK., ZhangC. and YangJ., A DNA Computing Model for the Graph Vertex Coloring Problem Based on a Probe Graph, Engineering4(1) (2018), 61–77.
46.
LiuX., HongZ., LiuJ., LinY., AlfonsoR.P., ZouQ. and ZengX., Computational methods for identifying the critical nodes in biological networks, Briefings in Bioinformatics21(2) (2020), 486–497.
47.
ByskovJ.M., Exact algorithms for graph colouring and exactsatisfiability, Operations Research Letters32 (2004), 547–556.
48.
ShaluM.A., VijayakumarS. and SandhyaT.P., On the complexity of cd-coloring of graphs, Discrete Applied Mathematics280 (2020), 171–185.
