CS 170 AlgorithmsSpring 2009 David Wagner HW 12Due May 1, 2:45pmInstructions: You may work in groups of up to 4 people, but make sure to list your study partnerson your homework. As always, you are required to write up your homeworks yourself, and youmust never share your write-ups with others.1. (25 pts.) 4-coloringThe 3-COLORING problem is as follows:Given: an undirected graph G = (V, E)Find: a valid 3-coloring c : V → {Red, Green, Blue}, or report that none existsThe 4-COLORING problem is as follows:Given: an undirected graph G = (V, E)Find: a valid 4-coloring c : V → {Red, Green, Blue,Yellow}, or report that none existsThese are both search problems. (Recall that c is a valid coloring if c(u) 6= c(v), for every edge(u,v) ∈ E.)Find a reduction from 3-COLORING to 4-COLORING. Use this reduction to prove that if thereis a polynomial-time algorithm for the 4-COLORING problem, then there is a polynomial-timealgorithm for 3-COLORING, too.2. (25 pts.) Hamiltonian pathThe HAMILTONIAN PATH problem is as follows:Given: a directed graph G = (V, E)Find: a Hamiltonian path, or report that none exists(A Hamiltonian path is a path that visits every vertex in V exactly once: no more, no less.) TheHAMILTONIAN CYCLE problem is as follows:Given: a directed graph G = (V, E)Find: a Hamiltonian cycle, or report that none existsA Hamiltonian cycle is a cycle that visits every vertex in V exactly once. (Recall that a cycle is apath that starts and ends at the same vertex.) These are both search problems. (These are basicallywhat the textbook calls the RUDRATA PATH and RUDRATA CYCLE problms, except that here wefocus on directed graphs.)CS 170, Spring 2009, HW 12 1(a) Prove that if you can solve HAMILTONIAN CYCLE in polynomial time, you can solve HAMIL-TONIAN PATH in polynomial time, by finding a reduction from HAMILTONIAN PATH toHAMILTONIAN CYCLE.(b) Prove that if you can solve HAMILTONIAN PATH in polynomial time, you can solve HAMIL-TONIAN CYCLE in polynomial time.3. (25 pts.) Longest PathHere is the LONGEST PATH problem:Given: a directed graph G = (V, E), where all edges have length 1Find: the longest simple path in G(Recall that a simple path is one where no vertex is repeated.) Also, here is the LONG PATHproblem:Given: a directed graph G = (V, E), where all edges have length 1; a minimum m ∈ NFind: a simple path whose length is at least m, or report that none existsLONG PATH is a search problem. A caution: LONGEST PATH does not seem to be a searchproblem: given a candidate path, it’s not clear how to verify in polynomial time whether it is thelongest possible simple path or not.(a) Suppose that Alice comes up with a polynomial-time algorithm A for LONGEST PATH. Ex-plain how to solve the LONG PATH problem in polynomial time, using A as a subroutine.(b) Suppose that Bob comes up with a polynomial-time algorithm B for LONG PATH. Explainhow to solve the LONGEST PATH problem in polynomial time, using B as a subroutine.(c) Find a reduction from HAMILTONIAN PATH to LONG PATH. In other words, prove that ifLONG PATH can be solved in polynomial time, then so can HAMILTONIAN PATH.4. (25 pts.) Bio-computingOne of the most remarkable developments in recent years has been development of powerful newmethods for DNA sequencing. These have partly built upon algorithmic advances in bio-computingand sequence assembly. In modern approaches to DNA sequencing, the genome to be sequencedconsists of a very long string made up of the four letters A, C, G, and T (these strings might be 108–109letters long); we are given many short fragments (substrings) from the string, but with no clueabout where in the string they came from, and possibly with some errors in these fragments; andthe goal of a sequence assembly algorithm is to reconstruct the full string. Work on this area hasled to many impressive algorithmic techniques that have helped make DNA sequencing feasible atlarge scale. This problem is intended to give you some taste of the computational challenges inthis area, in a greatly simplified form.Imagine that the genome to be sequenced consists of n` letters, and it has been split into n fragments(substrings), each of length ` = 2k. The first fragment is obtained from the letters at positions0..` − 1; the next from the letters at `..2` − 1; and so on, with no overlap between the fragments.We are given the set F = { f1, f2,..., fn} of fragments obtained in this way, but the order of themhas been scrambled so we have no idea which ficame from which position in the genome.CS 170, Spring 2009, HW 12 2Also, we are given a set C = {c1,. . ., cm} of additional strings, each of length `. Suppose thatwe have a pair of fragments fi, fj, and we want to know whether fjmight have been taken fromimmediately after fiin the original genome. If there is a string c ∈ C such that the first k letters ofc match the last k letters of fi, and such that the last k letters of c match the first k letters of fj, thenwe say the pair ( fi, fj) is corroborated by c. The intuition is that maybe c represents a fragmentof DNA that straddles the region where fiand fjappear in the genome, which would be consistentwith the hypothesis that fjcould have been taken from right after fi.We’d like to recover the original genome G, so we are going to look for a string of n` lettersthat is obtained by concatenating all the fragments of F in some order, with each fragment fromF used exactly once, where the fragments are arranged in an order so that each consecutive pairof fragments is corroborated by some element of C. In other words, we want to find a stringG = fi1fi2·· · finsuch that i1,i2,. . ., inis a permutation of 1, 2, . . . , n, and such that for each j ∈{1,2, . .. , n − 1}, the pair ( fij, fij+1) is corroborated by some element of C. Call any such string Ga corroborated assembly.The TOY SEQUENCING problem is then defined as:Given: sets F,C ⊆ {A,C,G, T }`Find: a corroborated assembly G ∈ {A,C,G, T }n`, or report that none existsProve that, if none of the search problems defined earlier in this homework can be solved in poly-nomial time, then there is no polynomial-time algorithm for the TOY SEQUENCING problem.Hint: Reduce one of the problems defined earlier in this homework (3-COLORING, 4-COLORING,HAMILTONIAN PATH, HAMILTONIAN CYCLE, or LONG PATH) to TOY SEQUENCING. Make sureto state which problem you are reducing from; then describe the reduction; then explain why thisreduction proves the desired result. To help the