# Solving Vertex Cover Problem Using DNA Tile Assembly Model

Authors: Zhihua Chen; Tao Song; Yufang Huang; Xiaolong Shi
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

DNA tile assembly models are a class of mathematically distributed and parallel biocomputing models in DNA tiles. In previous works, tile assembly models have been proved be Turing-universal; that is, the system can do what Turing machine can do. In this paper, we use tile systems to solve computational hard problem. Mathematically, we construct three tile subsystems, which can be combined together to solve vertex cover problem. As a result, each of the proposed tile subsystems consists ofΘ(1) types of tiles, and the assembly process is executed in a parallel way (like DNA’s biological function in cells); thus the systems can generate the solution of the problem in linear time with respect to the size of the graph.


---

## Body

## 1. Introduction

In the history of human designing computing devices, nature has provided brilliant ideas and frameworks to design intelligent computing models. Recently, due to the highly distributed and parallel features, bioinspired computing, including DNA computing [1–4], membrane computing [5–9], and neural-like computing [10–12], have received a lot of research attention. One of the famous results of biocomputing is Adleman's DNA computing model, which uses DNA molecule to solve a Hamiltonian path problem in tubes [1]. It demonstrated the feasibility of solving combinatorial problems by molecular computing, which used the vast parallelism of DNA molecule to do the combinatorial search among a large number of possible solutions. Till now, DNA computing has been heavily developed and used in different research fields, such as breaking cryptosystems [2, 13], hiding messages [4, 13], and computing functions [14]. However, most of the proposed DNA computing models are not autonomous, which require human intervention in each step, and the scale of the problems solved by DNA computing is restricted by the large numbers of laboratory procedures, error-prone reactions, and the time consumed. In the present work, we focus on a kind of DNA computing models, named DNA tile assembly model.DNA tile assembly model can automatically organize the components into defined aggregates with stable and robust structures [15]. Following the research line, it was theoretically proved that the tile assembly model of DNA computing is Turing-universal [2], while the experimental demonstration of computation using DNA tile was initialled in [16]. For general introduction of DNA tile assembly models, one can refer to the respective chapter of [2]. Recently, DNA assembly systems were also used in some other fields such as binary counters [17], computing Sierpinski triangles [18], and theoretically performing sum and product of two numbers [19].In this work, we use DNA tile assembly model to solve the famous NP-hard problem—vertex cover problem. Specifically, three tile self-assembly subsystems are constructed, which can constitute subsets of vertices, calculate the types of vertices in each subset, and count the number of vertices covered by the vertex in a subset, respectively. We combine the three subsystems to construct an integrated tile system that can solve vertex cover problems in linear time. As a result, we obtain that each subsystem consists ofΘ(1) types of tiles, and the system can generate the solution of the problem in linear time with respect to the size of the graph (due to the fact that each tile in the systems can do the assembly operation in a parallel way).


## 2. DNA Tile Self-Assembly Model

This section is started by recalling some useful notions and formal definition of DNA tile self-assembly model proposed in [19].LetΣ be a finite alphabet of binding domains, with null ∈Σ. A tile over Σ is a unit square with 4-tuple 〈σN,σE,σS,σW〉∈Σ4 indicating, respectively, the glues on the north, east, south, and west sides of the tile. A position is an element of ℤ2. The set of directions D={N,E,S,W} is a set of four functions from position to position, such that, for all positions (x,y), (x,y)∈ℤ2, then N(x,y)=(x,y+1), E(x,y)=(x+1,y), S(x,y)=(x,y-1), and W(x,y)=(x-1,y). The positions (x,y) and (x′,y′) are neighbors if and only if  ∃d∈D such that d(x,y)=(x′,y′). For a tile t, for d∈D, we refer to bdd(t) as the binding domain of tile t on d's side. According to this definition, tiles may not be rotated. A special tile, empty=〈null,null,null,null〉, represents the absence of all other tiles. The binding domains determine the interaction between tiles.A functiong:Σ×Σ→ℝ is a strength function denoting the strength of the binding domains. The function g can be calculated as
(1)g(σ,σ′)={+value,ifσ=σ′,0,otherwise.The value may be 0, 1, or 2 (resp., callednull, weak, and strong bonds).LetT be a set of tiles containing the empty tile. One configuration of T is a function A: ℤ×ℤ→T, and (x,y)∈A if and only if A(x,y)≠empty. One configuration is finite if and only if there is only a finite number of distinct positions (x,y)∈A. One tile system SYS is a triple 〈T,g,τ〉, with T being a finite set of tiles containing empty, g is a strength function, and τ∈ℕ is the temperature. If A is a configuration, then a tile t can attach to A at position (x,y) and produce a new configuration A′ if and only if(1)
(x,y)∉A,(2)
∑d∈D‍g(bdd(t),bdd-1(A(d(x,y))))≥τ,(3)
for all(u,v)∈Z2, (u,v)≠(x,y)⇒A′(u,v)=A(u,v),(4)
A′(x,y)=t.For a tile systemSYS=〈T,g,τ〉, a set of tiles Γ, and a seed configuration S:ℤ2→Γ, if the above conditions are satisfied, one may attach tiles of T to S. Configurations produced by repeated attachments of tiles from T are said to be produced by SYS on S. If this process terminates, the configuration is called the final configuration F.LetSYS=〈T,g,τ〉, and let S0 be a seed configuration such that SYS produces a unique final configuration F on S0, W0⊆2T×ℤ2 the set of all tile position pairs 〈t,(x,y)〉 such that t can attach to S0 at (x,y), and Si the configuration produced by adding all the elements of Wi-1 to Si-1 in one time step, where i=1,2,…. Number n is the smallest natural number such that Sn≡F, where n indicates the assembly time of S on S0 to produce F.


## 3. Solving Vertex Cover Problem by DNA Tile Assembly Model

The vertex cover tile system contains a set of tiles denoted byTvc, which can be divided into three disjoint subsets of tiles Tv,Tt, and Tk. (Mathematically, we have Tvc=Tv∪Tt∪Tk.) The functions of the tiles in distinguished subsets are different. Specifically, the tiles in Tv are nondeterministically chosen to constitute a vertices subset covering all the edges; the tiles in Tt calculate the types in the constituted vertices subset; the tiles in Tk can be used to count the number of vertices that are not in the constituted vertices subset and determine whether the result meets the requirement of the problem.The tile systems described above will usenV types of tiles to encode the vertices, as well as nE types of tiles to encode the edges in the graph. The set of the tiles used to encode the vertices and edges in the graph are denoted byΓseed={ee=〈null,ee,null,null〉,Vi=〈null,Vi,null,null〉,RR=〈null,RR,null,null〉,ViVj=〈ViVj,null,null,null〉,PP=〈PP,null,null,null〉,end=〈end,null,null,null〉,1=〈1,null,null,null〉∣1≤i,j≤nV}.The seeds are graphically shown in Figure1(a).(a) Tiles inΓseed with the name written on the top; (b) the meaning of the tiles in Tv to encode edges ViVj and vertex Vi or Vj.
(a)
(b)


### 3.1. Constituting One Subset

For a given seed configuration consisting of a given graph, we start by describing a tile system that can use tiles fromTv to nondeterministically constitute a vertices subset covering all the edges and to encode the vertices and edges with these tiles. The strategy used to encode an edge (Vi,Vj)∈E by tiles can be found from Figure 1(b), where the symbols on the sides of the tiles indicate the edge or vertex.In the following, we will give an example of a directed graphγ=(V,E) with 4 vertices (denoted by V1,V2,V3, and V4; see Figure 2(a)) to explain the process of constituting one subset. The seed configuration Sv is designed by the following binding domains: bdS(S(0,0))=V1V2, bdS(S(1,0))=V2V3, bdS(S(2,0))=V1V3, bdS(S(3,0))=V1V4, bdS(S(4,0))=PP, bdS(S(5,0))=1, bdS(S(6,0))=1, and bdS(S(7,0))=end; see Figure 2(b). And the SYSv produces a set of final configurations F on Sv such that F(0,1)=V1, F(1,1)=V3, F(2,1)=V1, F(3,0)=V1, F(4,0)=PP, F(5,0)=1; F(6,0)=1, and F(7,0)=end; see Figure 2(c).SYS
v produces a final configuration F on Sv such that F produces one subset of vertices. (a) An example graph; (b) the example seed configuration; (c) in this example, F constitutes one subset V1,V3,V1,V1.
(a)
(b)
(c)Note thatSYSv can produce all the final configurations in F on Sv, where F corresponds to the vertices subset covering all the edges.The tiles that are possible to attach toSv can produce a final configuration F that corresponds to the subset covering all the edges.(1)
F and Sv should agree at the first line with the corresponding binding domains.(2)
Note thatbdN(F(0,0))=V1V2, and the only tile with bdS(t)=V1V2 might attach here. There are two types of tiles such that bdS(t)=V1V2, so only these types of tiles can attach above. Furthermore, bdN(F(0,1))=V1 or V2, which indicates that the subset of vertices contains V1 or V2 (in this case, it is V1).(3)
It is easy to check thatbdN(F(1,0))=V2V3, so F(1,1)=V2 or V3 (in this case, the contained vertex is V3).(4)
It is easy to check thatbdN(F(2,0))=V1V3, so F(2,1)=V1 or V3 (in this case, the contained vertex is V1).(5)
It is easy to check thatbdN(F(3,0))=V1V4, so F(3,1)=V1 or V3 (in this case, the contained vertex is V1).(6)
The tilesbdN(F(4,0))=PP and bdS(t)=PP can attach here, where the tile {PP,RR} is attached indicating the boundary of subset is constitutes.(7)
, (8) The same as (6), it can be easily obtained thatbdS(F(5,0))=1,bdS(F(6,0))=1, so the tile {1,RR} is attached here.(9)
We havebdS(F(7,0))=end, and the only tile with bdS(t)=end may attach here, which show the boundary of the final configuration F.It is worth  pointing out that no more tiles may attach toF and one of subsets which satisfied the requests of the problem is {V1,V3,V1,V1}. Therefore, for all choices of subsets covering all edges, there exists a final configuration F produced by SYSv on Sv that constitutes a vertex subset. For different final configurations F′ produced by SYSv on Sv will constitute some random vertex subsets covering all edges.Lemma 1 (subsets assembly time lemma).
The assembly time of the final configurationF that constitutes vertex subset is Θ(nE).Proof.
For each tile inF to attach, a tile in a specific location can have attached before (either to the north or to the east). Hence, there is no parallelism in the assembly, and the assembly time equals the total number of tiles that attached, which is Θ(nE).


### 3.2. Type Calculation

After the tile system have nondeterministically assembled the representation of one vertices subset, we add tiles to implement the vertex type calculation. The meaning of tiles inTt is given in Figure 3.Figure 3
The meaning of tiles inTt, and Vi indicates the vertex Vi in the graph; Vi can be used to check the presentation of vertex Vi in the subset: if so, the tile outputs x=1, otherwise x=0.Each tileVi∈Tt is used to check the presentation of vertex Vi whether it is in the constituted vertices subset: if so, then output is 1, otherwise output is  0. The tile system SYSt can check the types of the vertices in the constituted subset. The example of the function of SYSt is shown in Figure 4, where the constituted subset is {V1,V3,V1,V1}. There are four gray tiles which check the vertex Vi whether it is present in the subset,  and the brown tiles complete the checking. The orange tiles are used to output the result: if the vertex is in the subset, the output is x=1, otherwise x=0.Figure 4
An example of the execution ofSYSt; the subset of vertices is {V1,V3,V1,V1}, and the checking result is x=1010.Theorem 2.
LetΣt={Vi,i1,i0,0,PP,RR,ee,ix,x∣i∈{1,2,…,n},x∈{0,1}}, τv=2, and  gdivisor=(σ,σ)=1 for σ∈Σt, Tt a set of tiles, St the final configuration produced by SYSv on Sv that constitutes the subset of vertices, Fv unique final configuration (by which one can get the computing result), St the configuration such that
(2)∀x,y∈Tt,Fv(x,y)≠empty⟹St(x,y)=Fv(x,y),
and SYSt=〈Tt,gt,τt〉.Proof.
LetSub be the constituted subset and Vi any vertex in the graph with i∈{1,2,…,n}. If Vi∈Sub, then xi=1, otherwise xi=0. The tile system SYSt computes the final configuration Fv produced by SYSv, and SYSt will produce a unique final configuration Ft on St. The orange tiles (similar to those in Figure 4) can output the checking result and cooperate with other tiles. Therefore, the tile system SYSt is able to check the type of the tiles and output the result during the self-assembly progress.Corollary 3 (checking assembly time).
The assembly time forSYSt starting from one seed that encodes vertices and edges is Θ(nV+nE).Proof.
The tiles inFt will attach in a strict order; that is, only the corner position may be attached to one certain type of tiles. So the tiles in the diagonal positions perform the processes of computing in parallel. With the parallelism, the resulting configuration is the nV×nE rectangle, and the assembly time is nV+nE steps.


### 3.3. Checking the Number of Vertices in the Subset

With the two tile subsystems described above (one generates a random vertices subset, and the other one checks whether the vertex type is contained in the subset or not), we design one more tile subsystem to compute the number of vertices in the subset and to determine whether the number of vertices is less thanK or not. The meaning of tiles in Tk is shown in Figure 5, where the dark-green tiles with variables i,j,m,n, and y are used to finish the vertex types counting in the subset; the light-blue tiles are used to check whether the number of vertex types in the subset is less than K or not; the red tiles with “NO” or “OK” serve as the mark to show the result of the problem, and the blue tiles will terminate the checking and mark the final configuration F produced.Figure 5
The meaning of tiles inTk with i,j,m,n,y∈{0,1}.Theorem 4.
LetΣk={0,1,00,01,10,11,ok,no,end,RR}, gk(σ,σ)=1 for all σ∈Σk, τk=1, Tk a set of tiles of the form shown in Figure 5, Sk the final configuration produced by the tile system SYSt on St that outputs each vertex present in the subset or not, Fk the unique final configuration (by which one can get the computing result), Sk the configuration such that
(3)∀x,y∈Tt,Fv(x,y)≠empty⟹Sk(x,y)=Fv(x,y),
and SYSk=〈Tk,gk,τk〉. It holds that SYSk produces a unique final configuration Fk, and the number of vertex types in the subset is less than K if and only if Fk(nE+(nV-K+1,1+nV+1))=OK.Proof.
If the “OK” tile is ever to attach, then it should attach in position(nE+(nV-K)+1,1+nV+1). Since the sum of the g values of the binding domains is exactly 2, it can only match its neighbors on all sides with nonnull binding domains to attach at temperature 2. Furthermore, the tile with a south binding domain “end” and a west binding domain “ok,” matching the assembly's north binding domain and the east binding domain, is the “OK” tile, so it can attach only when the light-blue tiles “ok” have attached in position from (nE+1,1+nV+1) to (nE+(nV-K),1+nV+1). Once there is one position attaching “no,” then the end position will attach “NO” tile.
Let us consider the unique final configurationFk. The “ok” tile can attach at position (nE+1,1+nV+1), and at west of the tile there is an east binding domain “ok.” Therefore, the tiles at positions (nE+i,1+nV+1) with i=1,2,…(nV-K) should have the output of east binding domain “ok.” It indicates that at least (nV-K) vertices are not in the constituted subset. If the binding domain “no” occurs, it means that the number of vertex types in the constituted subset is more than K. In this case, the “No” tile will attach at position (nE+(nV-K)+1,1+nV+1). For the produced subset, an “OK” tile can attach at position (nE+(nV-K)+1,1+nV+1) to Fk if and only if the number of vertex types in the constituted subset is not more than K.Following the example given above, the final configurationFk produced by the tile system SYSk is shown in Figure 6.Figure 6
The final configurationFk produced by the tile system SYSk for the example of Figure 4.Corollary 5 (calculating assembly time).
The assembly time of the final configurationF produced by SYSk on Sk that draws the conclusion of the number of vertex types in the subset whether more than K or not is Θ((nV-K)+nV).


### 3.4. Solving Vertex Cover Problem Using DNA Tile Assembly System

Till now, we have defined three tile subsystems that perform the necessary pieces of solving the vertex cover problem. We now combine them into one single system SYSVC and argue that SYSVC  is a tile system solving the vertex cover problem.If a tile system is the combination of three distinct tile subsystems, the behavior of the combined systems contains the behaviors of the subsystems. Although the tiles from different subsystems can interfere with each other, according to the design of the subsystemsSYSv, SYSt, and SYSk, they can work together without interfering. For the most part, each subsystem uses a disjoint set of binding domains, sharing binding domains only when tiles from the different subsystems are designed to interact. As a result, the tiles from each subsystem have a particular set of positions where they can attach. Specifically, tiles from Tv can only attach in row 1, tiles from Tt can only attach in the rectangle defined by the same color rectangle, and tiles from Tk can only attach in the same color rectangle too. Therefore, the tiles from different subsystems do not interfere with each other; see Figure 7. As explained above, we can easily obtain the following theorem.Figure 7
The construction of systemSYSC and the location of subsystems SYSv, SYSt, and SYSk.Theorem 6 (vertex cover theorem).
LetΣVC=Σv∪Σt∪Σk, TVC=Tv∪Tt∪Tk; gVC agrees with gv, gt, and gk on their respective domains, and τVC=2. It holds that the system SYSVC=〈TC,gC,τC〉 is a tile system solving the vertex cover problem.Proof.
Consider a directed graphγ=(V,E) with n vertices denoted by V1,V2,…,Vn, and a positive integer K≤card(V). The number of vertices is denoted by nV, and the number of edges is nE. We assume that 0≤a<nE, SVC(a,0)=ViVj, for all (Vi,Vj)∈E; 1≤i,j≤nV, SVC(nE,0)=PP, 1≤b<nV-K, SVC(nE+b,0)=1, and  SVC(nE+(nV-K)+1,0)=end.
For all edges in the graph, tiles fromTC will attach to SC as follows: the tiles from Tv nondeterministically attach to constitute one vertex subset covering all edges in row 1, as described in Section 3.1. According to Theorem 2, the tiles from Tt attach, in the gray rectangle denoted in  Figure 7, to check which vertex is obtained in the subset and output the results. Finally, tiles from Tk attach, in dark-green rectangle denoted in the Figure 7, such that, by Theorem 4, the “OK” tile attaches only when at least (nV-K) vertices are not present in the constituted subset; that is, the vertex number of the subset is no more than K. Therefore, SYSVC can nondeterministically and identifiably solve the vertex cover problem.Corollary 7 (vertex cover assembly time).
The assembly time forSVC to produce a final configuration F that draws the conclusion of the number of vertex types in the subset whether more than K or not is Θ(2nV+nE-K).


## 3.1. Constituting One Subset

For a given seed configuration consisting of a given graph, we start by describing a tile system that can use tiles fromTv to nondeterministically constitute a vertices subset covering all the edges and to encode the vertices and edges with these tiles. The strategy used to encode an edge (Vi,Vj)∈E by tiles can be found from Figure 1(b), where the symbols on the sides of the tiles indicate the edge or vertex.In the following, we will give an example of a directed graphγ=(V,E) with 4 vertices (denoted by V1,V2,V3, and V4; see Figure 2(a)) to explain the process of constituting one subset. The seed configuration Sv is designed by the following binding domains: bdS(S(0,0))=V1V2, bdS(S(1,0))=V2V3, bdS(S(2,0))=V1V3, bdS(S(3,0))=V1V4, bdS(S(4,0))=PP, bdS(S(5,0))=1, bdS(S(6,0))=1, and bdS(S(7,0))=end; see Figure 2(b). And the SYSv produces a set of final configurations F on Sv such that F(0,1)=V1, F(1,1)=V3, F(2,1)=V1, F(3,0)=V1, F(4,0)=PP, F(5,0)=1; F(6,0)=1, and F(7,0)=end; see Figure 2(c).SYS
v produces a final configuration F on Sv such that F produces one subset of vertices. (a) An example graph; (b) the example seed configuration; (c) in this example, F constitutes one subset V1,V3,V1,V1.
(a)
(b)
(c)Note thatSYSv can produce all the final configurations in F on Sv, where F corresponds to the vertices subset covering all the edges.The tiles that are possible to attach toSv can produce a final configuration F that corresponds to the subset covering all the edges.(1)
F and Sv should agree at the first line with the corresponding binding domains.(2)
Note thatbdN(F(0,0))=V1V2, and the only tile with bdS(t)=V1V2 might attach here. There are two types of tiles such that bdS(t)=V1V2, so only these types of tiles can attach above. Furthermore, bdN(F(0,1))=V1 or V2, which indicates that the subset of vertices contains V1 or V2 (in this case, it is V1).(3)
It is easy to check thatbdN(F(1,0))=V2V3, so F(1,1)=V2 or V3 (in this case, the contained vertex is V3).(4)
It is easy to check thatbdN(F(2,0))=V1V3, so F(2,1)=V1 or V3 (in this case, the contained vertex is V1).(5)
It is easy to check thatbdN(F(3,0))=V1V4, so F(3,1)=V1 or V3 (in this case, the contained vertex is V1).(6)
The tilesbdN(F(4,0))=PP and bdS(t)=PP can attach here, where the tile {PP,RR} is attached indicating the boundary of subset is constitutes.(7)
, (8) The same as (6), it can be easily obtained thatbdS(F(5,0))=1,bdS(F(6,0))=1, so the tile {1,RR} is attached here.(9)
We havebdS(F(7,0))=end, and the only tile with bdS(t)=end may attach here, which show the boundary of the final configuration F.It is worth  pointing out that no more tiles may attach toF and one of subsets which satisfied the requests of the problem is {V1,V3,V1,V1}. Therefore, for all choices of subsets covering all edges, there exists a final configuration F produced by SYSv on Sv that constitutes a vertex subset. For different final configurations F′ produced by SYSv on Sv will constitute some random vertex subsets covering all edges.Lemma 1 (subsets assembly time lemma).
The assembly time of the final configurationF that constitutes vertex subset is Θ(nE).Proof.
For each tile inF to attach, a tile in a specific location can have attached before (either to the north or to the east). Hence, there is no parallelism in the assembly, and the assembly time equals the total number of tiles that attached, which is Θ(nE).


## 3.2. Type Calculation

After the tile system have nondeterministically assembled the representation of one vertices subset, we add tiles to implement the vertex type calculation. The meaning of tiles inTt is given in Figure 3.Figure 3
The meaning of tiles inTt, and Vi indicates the vertex Vi in the graph; Vi can be used to check the presentation of vertex Vi in the subset: if so, the tile outputs x=1, otherwise x=0.Each tileVi∈Tt is used to check the presentation of vertex Vi whether it is in the constituted vertices subset: if so, then output is 1, otherwise output is  0. The tile system SYSt can check the types of the vertices in the constituted subset. The example of the function of SYSt is shown in Figure 4, where the constituted subset is {V1,V3,V1,V1}. There are four gray tiles which check the vertex Vi whether it is present in the subset,  and the brown tiles complete the checking. The orange tiles are used to output the result: if the vertex is in the subset, the output is x=1, otherwise x=0.Figure 4
An example of the execution ofSYSt; the subset of vertices is {V1,V3,V1,V1}, and the checking result is x=1010.Theorem 2.
LetΣt={Vi,i1,i0,0,PP,RR,ee,ix,x∣i∈{1,2,…,n},x∈{0,1}}, τv=2, and  gdivisor=(σ,σ)=1 for σ∈Σt, Tt a set of tiles, St the final configuration produced by SYSv on Sv that constitutes the subset of vertices, Fv unique final configuration (by which one can get the computing result), St the configuration such that
(2)∀x,y∈Tt,Fv(x,y)≠empty⟹St(x,y)=Fv(x,y),
and SYSt=〈Tt,gt,τt〉.Proof.
LetSub be the constituted subset and Vi any vertex in the graph with i∈{1,2,…,n}. If Vi∈Sub, then xi=1, otherwise xi=0. The tile system SYSt computes the final configuration Fv produced by SYSv, and SYSt will produce a unique final configuration Ft on St. The orange tiles (similar to those in Figure 4) can output the checking result and cooperate with other tiles. Therefore, the tile system SYSt is able to check the type of the tiles and output the result during the self-assembly progress.Corollary 3 (checking assembly time).
The assembly time forSYSt starting from one seed that encodes vertices and edges is Θ(nV+nE).Proof.
The tiles inFt will attach in a strict order; that is, only the corner position may be attached to one certain type of tiles. So the tiles in the diagonal positions perform the processes of computing in parallel. With the parallelism, the resulting configuration is the nV×nE rectangle, and the assembly time is nV+nE steps.


## 3.3. Checking the Number of Vertices in the Subset

With the two tile subsystems described above (one generates a random vertices subset, and the other one checks whether the vertex type is contained in the subset or not), we design one more tile subsystem to compute the number of vertices in the subset and to determine whether the number of vertices is less thanK or not. The meaning of tiles in Tk is shown in Figure 5, where the dark-green tiles with variables i,j,m,n, and y are used to finish the vertex types counting in the subset; the light-blue tiles are used to check whether the number of vertex types in the subset is less than K or not; the red tiles with “NO” or “OK” serve as the mark to show the result of the problem, and the blue tiles will terminate the checking and mark the final configuration F produced.Figure 5
The meaning of tiles inTk with i,j,m,n,y∈{0,1}.Theorem 4.
LetΣk={0,1,00,01,10,11,ok,no,end,RR}, gk(σ,σ)=1 for all σ∈Σk, τk=1, Tk a set of tiles of the form shown in Figure 5, Sk the final configuration produced by the tile system SYSt on St that outputs each vertex present in the subset or not, Fk the unique final configuration (by which one can get the computing result), Sk the configuration such that
(3)∀x,y∈Tt,Fv(x,y)≠empty⟹Sk(x,y)=Fv(x,y),
and SYSk=〈Tk,gk,τk〉. It holds that SYSk produces a unique final configuration Fk, and the number of vertex types in the subset is less than K if and only if Fk(nE+(nV-K+1,1+nV+1))=OK.Proof.
If the “OK” tile is ever to attach, then it should attach in position(nE+(nV-K)+1,1+nV+1). Since the sum of the g values of the binding domains is exactly 2, it can only match its neighbors on all sides with nonnull binding domains to attach at temperature 2. Furthermore, the tile with a south binding domain “end” and a west binding domain “ok,” matching the assembly's north binding domain and the east binding domain, is the “OK” tile, so it can attach only when the light-blue tiles “ok” have attached in position from (nE+1,1+nV+1) to (nE+(nV-K),1+nV+1). Once there is one position attaching “no,” then the end position will attach “NO” tile.
Let us consider the unique final configurationFk. The “ok” tile can attach at position (nE+1,1+nV+1), and at west of the tile there is an east binding domain “ok.” Therefore, the tiles at positions (nE+i,1+nV+1) with i=1,2,…(nV-K) should have the output of east binding domain “ok.” It indicates that at least (nV-K) vertices are not in the constituted subset. If the binding domain “no” occurs, it means that the number of vertex types in the constituted subset is more than K. In this case, the “No” tile will attach at position (nE+(nV-K)+1,1+nV+1). For the produced subset, an “OK” tile can attach at position (nE+(nV-K)+1,1+nV+1) to Fk if and only if the number of vertex types in the constituted subset is not more than K.Following the example given above, the final configurationFk produced by the tile system SYSk is shown in Figure 6.Figure 6
The final configurationFk produced by the tile system SYSk for the example of Figure 4.Corollary 5 (calculating assembly time).
The assembly time of the final configurationF produced by SYSk on Sk that draws the conclusion of the number of vertex types in the subset whether more than K or not is Θ((nV-K)+nV).


## 3.4. Solving Vertex Cover Problem Using DNA Tile Assembly System

Till now, we have defined three tile subsystems that perform the necessary pieces of solving the vertex cover problem. We now combine them into one single system SYSVC and argue that SYSVC  is a tile system solving the vertex cover problem.If a tile system is the combination of three distinct tile subsystems, the behavior of the combined systems contains the behaviors of the subsystems. Although the tiles from different subsystems can interfere with each other, according to the design of the subsystemsSYSv, SYSt, and SYSk, they can work together without interfering. For the most part, each subsystem uses a disjoint set of binding domains, sharing binding domains only when tiles from the different subsystems are designed to interact. As a result, the tiles from each subsystem have a particular set of positions where they can attach. Specifically, tiles from Tv can only attach in row 1, tiles from Tt can only attach in the rectangle defined by the same color rectangle, and tiles from Tk can only attach in the same color rectangle too. Therefore, the tiles from different subsystems do not interfere with each other; see Figure 7. As explained above, we can easily obtain the following theorem.Figure 7
The construction of systemSYSC and the location of subsystems SYSv, SYSt, and SYSk.Theorem 6 (vertex cover theorem).
LetΣVC=Σv∪Σt∪Σk, TVC=Tv∪Tt∪Tk; gVC agrees with gv, gt, and gk on their respective domains, and τVC=2. It holds that the system SYSVC=〈TC,gC,τC〉 is a tile system solving the vertex cover problem.Proof.
Consider a directed graphγ=(V,E) with n vertices denoted by V1,V2,…,Vn, and a positive integer K≤card(V). The number of vertices is denoted by nV, and the number of edges is nE. We assume that 0≤a<nE, SVC(a,0)=ViVj, for all (Vi,Vj)∈E; 1≤i,j≤nV, SVC(nE,0)=PP, 1≤b<nV-K, SVC(nE+b,0)=1, and  SVC(nE+(nV-K)+1,0)=end.
For all edges in the graph, tiles fromTC will attach to SC as follows: the tiles from Tv nondeterministically attach to constitute one vertex subset covering all edges in row 1, as described in Section 3.1. According to Theorem 2, the tiles from Tt attach, in the gray rectangle denoted in  Figure 7, to check which vertex is obtained in the subset and output the results. Finally, tiles from Tk attach, in dark-green rectangle denoted in the Figure 7, such that, by Theorem 4, the “OK” tile attaches only when at least (nV-K) vertices are not present in the constituted subset; that is, the vertex number of the subset is no more than K. Therefore, SYSVC can nondeterministically and identifiably solve the vertex cover problem.Corollary 7 (vertex cover assembly time).
The assembly time forSVC to produce a final configuration F that draws the conclusion of the number of vertex types in the subset whether more than K or not is Θ(2nV+nE-K).


## 4. Conclusion

In this work, the vertex cover problem is considered to be solved by tile assembly system. Function package is a common technique usually used in programming by general digital computers. Herein, we have “packaged” the proposed three tile subsystems in tile self-assembly model:SYSv, SYSt, and SYSk, and combine them together to form SYSVC with such functions of generating subsets, computing functions, and checking results. For future work, it is still possible to decrease the number of tile types used in the tile systems.



---

*Source: 407816-2013-12-10.xml*