MIT International Journal of Computer Science & Information Technology, Vol. 2, No. 1, Jan. 2012, pp.

(16-18) 16
ISSN 2230-7621 MIT Publications

Towards the Solution of

Minimum Vertex Cover Problem
Hari Om Sharan Sumit Chaudhary
Department of Computer Science Department of Computer Science
COE, Teerthankar Mahaveer University COE, Teerthankar Mahaveer University
Moradabad, (India) Moradabad, (India)
e-mail: [email protected] e-mail: [email protected]
Swarna Chaudhary Shivangi Dhall
Department of Computer Science Department of Computer Science
MIT, Moradabad, (India) MIT, Moradabad, (India)
e-mail: [email protected] e-mail: [email protected]

ABSTRACT
DNA Computing is an alternative method for computations. It is based on the observation that in general it is possible to
design of series of biochemical experiments involving DNA molecules which is equivalent to processing information
encoded in these molecules. Cooks Theorem tells that if one algorithm for an NP-complete or an NP-hard problem will be
developed, then other problems will be solved by means of reduction to that problem. The minimum vertex cover problem
is a classic graph optimization problem and has been shown to be NP-Complete. In this paper, we propose a DNA algorithm
for solving the minimum vertex-cover problem.
Keywords: DNA Computing; NP-complete problems; NP-hard problems; Minimum Vertex Cover Problem; Cooks Theorem.

INTRODUCTION as bio-operations, will be involved to manipulate DNA strands

in a test tube in order to simulate arithmetical and logical
DNA computing is one interdisciplinary research area that is operations. It is estimated that a mix of 1018 DNA strands
growing fast since DNA molecules are implemented in a could operate 104 times faster than the speed of a todays
computational process. One of the main objectives of this advanced supercomputer [3].
research area is to produce, in near future, a biologically
Vertex cover is NP-complete; we dont expect to find a
inspired computer based on DNA molecules to replace or at
polynomial time algorithm for finding a minimum size vertex
least beneficially complement with a silicon based computer.
cover. The size of a vertex cover produced by the approxi-
Since R. Feynman has suggested to construct a computer from
mation algorithm is at most twice the minimum size of a vertex
molecules in 1964 [1]. It took 30 years till Adleman in 1994
cover. The vertex cove problem is to find a vertex cover of
making proof of the principle study that DNA molecules can
minimum size in a given undirected graph. We call such a
solve an NP problem of Hamiltonian Path Problem (HPP)
vertex cover an optimal vertex cover. This problem is the
through bio-chemical procedure [2].
optimization version of an NP-complete decision problem.
DNA is a basic storage medium for all living cells. The
Given the common belief that NP-hard optimization
main function of DNA is to absorb and transmit the data of
problems cannot be solved exactly in polynomial time, much
life for billions years. Roughly, it is around 10 trillions of DNA
research has been devoted in the past twenty years to drive
molecules could fit into a space, the size of a marbles. Since
efficient approximation algorithm. i.e. algorithms that deliver
all these molecules can process data simultaneously,
solutions whose value is guarantee to be within some
theoretically, we can calculate 10 trillions times simultaneously
multiplicative factor from the optimum. In order to evaluate
in a small space at one time. DNA computing is more generally
the performance guarantees of such approximation algorithms,
known as molecular computing. It is interdisciplinary field
it is important to understand how far we can go. i.e. to prove,
where it is a combination of biology, chemistry, and
for any approximable problem, which is the best approximation
mathematics and computer science. Computing with DNA
achievable in polynomial time.
offers a completely new paradigm for computation. The main
idea of computing with DNA is to encode data in a DNA strand In the general case, a very simple 2-approximate algorithm
form, and laboratory techniques of molecule biology, called has been known for thirty years [4], and no better
MIT International Journal of Computer Science & Information Technology, Vol. 2, No. 1, Jan. 2012, pp. (16-18) 17
ISSN 2230-7621 MIT Publications

approximation algorithm has been found until now. Slightly The vertex-cover problem is to find a vertex cover of
better approximation guarantees are achievable over bounded minimum size in a given graph. Restating this optimization
degree graphs [5]. On the negative side, the minimum vertex problem as a decision problem, we wish to determine whether
cover problem has been shown to be Max SNP-hard even when a graph has a vertex cover of a given size k.
restricted to graphs with maximum degree 3 by Papadimitriou Since VERTEX-COVER is NP-complete, we dont expect
and Yannaakasis [6]. Their reduction is from MAX 3-SAT and to find a polynomial-time algorithm for finding a minimum-
uses explicit construction of expander graphs [7]. Combining size vertex cover.
this reduction, the non-approximability results by Ballare et
al. [8] and the best known explicit construction of expanders DNA algorithm for Vertex Cover Problem
[9], one can show that Minimum vertex cover is not 1.00036-
The following DNA algorithm is proposed to solve the vertex-
approximableon bounded degree graphs. Ballare et al. [8] give
cover problem:
a 1.0688 lower bound for the general minimum vertex cover
problem by using a different technique, namely, they reduce Step 1: Encoding of the Problem in DNAs
directly from the computation of a verifier using a somehow
Encoding the vertices: For each vertex, synthesize a
complementary version of the FLGSS reduction [10].
random 10-based palindrome DNA strand where Vi represents
However, their method does not apply when classes of graphs
the ith vertex.
in which a fixed bound on the maximum degree or some other
density constraints are considered. Encoding the edges: For each directed edge Vi Vj,
synthesize a 10-base DNA strand consisting complementary
of 3 5-mer sequence of Vi and complementary of 5 5-mer
MINIMUM VERTEX COVER PROBLEM sequence of Vj .
The minimum vertex cover problem arises in various important Each vertex Vi in the graph has to be associated with a
applications, including in multiple sequence alignments in designed palindrome 10-mer sequence of DNA denoted
computational biochemistry. Several approaches, such as the by Vi. For each edge Vi Vj in the graph, an oligonucliotide
use of a parameterized algorithm [11] and the use of a simulated 3 5-mer complementary sequence of Vi followed by 5 5-mer
annealing algorithm [12], have been developed to solve this complimentary sequence of Vj to be synthesized.
problem. Since DNA computing, which uses parallel
computing, can be used to solve large problems, this study Step 2: Create an Empty Set for Vertices and take a Copy of
n
introduces an alternative molecular computing approach to Edge Set
solve the minimum vertex cover problem.
i =1
aijxi 1
After the completing of Step 1 (i.e. encoding the vertices
A vertex cover for a graph G is a set of vertices V so that and edges) we create an empty set for vertices (V) and edges
every edge of G is incident to at least one vertex in V. Namely, (E) after that we will create a copy of edge set (E).
V covers the edges of G. The Minimum Vertex Cover problem
is to find the minimum set of vertices that cover all edges. Step 3: Repeatedly Picks an Edge (Vi, Vj) from the Copy of
Given an undirected graph G = (V, E), m = |V| and n = |E| are Edge Set
defined as the numbers of vertices and edges, respectively. A To avoid repetition of the nodes in the DNA strands an
vertex edge incidence matrix A = (aij) of G is defined as aij = 1 effective method, SSCP has to be used. The mobility in gel
if edge j is incident to vertex i; otherwise aij = 0, with i = 1, , electrophoresis of double stranded DNAs of a given length is
m; j = 1, , n. The Minimum Vertex Cover problem can be relatively independent of nucleotide sequence. In contrast, the
stated as follows. mobility of single strands can vary considerably as a result of
n
only small changes in nucleotide sequence. This fact led to
minimize xi the development of single-stranded conformation
polymorphism (SSCP) techniques [13]. SSCP is the simplest
i =1
and most used method of mutation detection. PCR is used to
subject to and xi {0, 1}, with I = 1, , amplify the region of interest and the resultant DNA can be
separated as single-stranded molecules by electrophoresis in
m; j = 1, , n a no denaturing polyacrylamide gel. A strand of single-stranded
DNA folds differently from another if it differs by a single
base, and it is believed that changes of structure of the DNA
Vertex Cover Problem is NP-Complete results in different motilities for the two strands. These
A vertex cover of an undirected graph G = (V, E) is a subset V mutations can be detected as the appearance of new bands on
V such that if (u, v) E, then u V or v V (or both). That is, auto radiograms (radioactive detection), by silver staining of
each vertex covers its incident edges, and a vertex cover for bands or the use of fluorescent PCR primers which are
G is a set of vertices that covers all the edges in E. The size of subsequently detected by an automated DNA sequencer (non-
a vertex cover is the number of vertices in it. radioactive detection).
MIT International Journal of Computer Science & Information Technology, Vol. 2, No. 1, Jan. 2012, pp. (16-18) 18
ISSN 2230-7621 MIT Publications

Since all the nodes encoded are palindrome DNA strands, REFERENCES
repetition of the nodes can lead to formation of Hairpin loop
structures [14]. These hairpins like structures have to be [1] R.P. Feynman, Miniaturization, New York, Reinhold,
pp. 282-296, 1961
eliminated from single stranded DNA strands by the above
process. The hairpin loop strands are not considered for [2] L.M. Adleman, Molecular computation of solutions to
combinatorial problems, Sciences, Vol. 266, No. 5187,
deriving the solution.
pp. 1021-1024, 1994.
Step 4: Amplification of DNA Paths by PCR [3] L. Kari, From micro-soft to bio-soft: Computing with DNA,
Biocomputing and Emergent Computation: Proc. of the
Amplification of DNA paths that begin with vertex source
BCEC97, World Scientific, Skovde, Sweden, pp. 146-164,
and end with vertex destination to be performed. Two specific 1997.
primers that can anneal with source vertex and destination
[4] F. Gavril. Manuscript cited in [18], 1974.
vertex are to be added to the PCR reaction.
[5] B. Monien and E. Speckenmeyer. Some further Approximation
Step 5: Mark the Endpoints Vi and Vj to Empty Set algorithms for the vertex cover problem. In proceedings of
CAAP83, pages 341-349. LNCS 159, Springer Verlag, 1983.
In step 4 we picked an edge (Vi, Vj) from the copy of edge
[6] C.H. Papadimitriou and M. Yannakakis. Optimization,
set (E), here we mark its endpoints say Vi and Vj to the set of
Approximation and Complexity classes. Journal of Computer
vertices which was created in step 2 as an empty set. and System Sciences, 43:425-440, 1991. Preliminary version
Step 6: Delete the Edges from the Copy of Edge Set in Proc. of STOC88.
In this step we will remove all the edges from the copy of [7] O. Gabber and J. Galil. Explicit construction of linear sized
edge set (E) that are covered by either vertex Vi or vertex Vj. super concentrators. Journal of Computer and System
And this process will repeat until the copy of edge set will be Sciences, 22:407-425, 1981.
empty. [8] M. Bellare, O. Goldriech and M. Sudan. Free bits, PCPs and
non-approximability-towards tight results (3 rd version).
Step 7: Sequencing of DNA Strands Technical Report TR95-24 Electronic Colloquium on
Computational Complexity, 1995. Priliminary version in Proc.
The strands obtained in the step 5 are now to be sequenced.
of FOCS95.
The weights of the strands are determined by reading the
sequence. The set having the minimum number of vertices [9] A. Lubotzky, R. Philips and P. Sarnak. Ramanujan Graphs.
Combinatorica, 8:261-277, 1988.
that covers entire graph is our desired solution.
[10] U. Feige, S. Goldwasser, L. Lovasz, S. Safra and M. Szegedy.
Approximating clique is almost NP-complete. In Proceeding
CONCLUDING REMARK of the 32nd IEEE Symposium on Foundations of Computer
Science, pp. 2-12, 1991.
This paper has proposed a faster approach for finding the
[11] R.G. Downey and M.R. Fellows, Fixed parameter tractability
solution for minimum vertex cover problem using DNA
and completeness II: completeness for W[1] Theory, Comp.
Computing. Because the DNA Computing, due to its high Sci., Vol. 141, 1995, pp.1-2.
degree of parallelism, can overcome the difficulties that may
[12] X. Xu and J. Ma, An efficient simulated annealing algorithm
cause the problem intractable on silicon computers, however
for the minimum vertex cover problem, Neurocomputing,
using DNA computing principles for solving simple problems Vol. 69, 2006, pp. 913-916.
may not be suggestible. To make the DNA computing
[13] Martyn Amos, Gheorghe Paun, Grzezorg, Rozenberg and Arto
applicable in practice further research in both fields- Computer Salomaa, Topics in the theory of DNA computing,
science and biology is necessary. Computer science needs Theoretical computer science, 287, 2000, 3-38.
to develop more elaborate DNA algorithms, while better
[14] K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S.Yokoyoma,
enzymes and protocols are needed to from biology to T. Yokomori and M. Hagiya, Molecular computation by
manipulate DNA molecules more selectively with minimal Hairpin formation, Science, 288, 2000, 1223-1226.
errors.