Question 2:

A directed Hamiltonian cycle DHC in a directed graph G = (V, E) is a directed cycle of length n =|V|, where |V| is the number of vertices in G. So, the cycle goes through every vertex exactly once and then returns to the starting vertex. The DHC problem is to determine if a given directed graph G has a directed Hamiltonian cycle. Show that DHC is NP-Hard.                         (20 marks)

ANSWER:

Directed Hamiltonian Cycle:
The first step toward solving the DHC problem lies in finding a way to represent the components of a directed graph G = (V,E) (i.e. vertices and edges). Next the operations needed to determine the existence of a valid Hamiltonian cycle are presented.

Oligo Selection:
We’ll choose unique, 20-base oligos to represent each vertex vi V. Wel’ll notate the n vertex oligos as x1y1… xnyn where xi represents the 10 bases oriented at the 5’ end and yi is the following 10 bases ending at the 3’ end. The edge oligos will be choses based on the vertices that define them using the following scheme. For each edge (vi, vj ) E, we’ll use yixj to represent it, with one exception. For each edge that includes the starting vertex vs, we’ll use the entire complement of xsys as follows. For an edge leaving vs, (vs, vj), we’ll use xsysxj and for an edge entering vs (vi,vs), we’ll use yixsys. When these oligos are placed in solution, complementary oligos will anneal to one another, resulting in valid paths on G. How does this work? Observe that each edge oligo, yi xj , will anneal to its respective vertex oligos, xi yi and xj yj, to form xi yixj yj. Furthermore, if there is an edge yixk and vertex xk yk, a path of length two is created resulting in xi yixj yjIk yk. It would be prudent now to explain why the modified representation of edges containing vs was chosen. Recall that we’re specifically looking for paths that begin and end with vs. So when a path contains an edge leaving vs say (vs, vj ), it will form a strand of the form xsys xj yj. The only possible oligo that can anneal to the beginning of this strand is xsys, forcing strands containing this edge to represent paths beginning with vs. The same logic was used for our representation of edges entering vs, resulting in paths that must terminate at vs.

Read Full Post HERE

<< Previous Answer || Index Assignments || Next Answer>>