282 Design & Analysis of Efficient Algorithms - Fall 2013
Instructor: Henry Kautz
Assignment 5
You should complete these problems, but they will not be handed in or graded. The exam on the last day of class (Dec 12) will be based on this material. The solutions to the problems will be discussed in the workshops, but note that if you do not spend time on your own working on the problems you will not succeed on the exam.
[DVP 8.1] Optimization versus search.
Recall the traveling salesman problem:
TSP
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b, if such a tour exists.
The optimization version of this problem asks directly for the shortest tour.
TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.
Show that if TSP can be solved in polynomial time, then so can TSP-OPT.
[DVP 8.2] Search versus decision.
Suppose you have a procedure which runs in polynomial time and tells you whether or not a graph has a Rudrata path. Show that you can use it to develop a polynomialtime algorithm for Hamiltonian Path (in DVP called a RUDRATA PATH) (which returns the actual path, if it exists).
[DVP 8.3] STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY SAT is NP-complete.
Next, show that if k is any fixed constant, then the problem can be solved in polynomial time. For example, defined STINGY-K3 SAT as the problem of determining if a formula has an assignment in at which at most 3 variables are true. STINGY-3 SAT can be solved by an algorithms whose time is bounded by f(n), where n is the length of the formula and f is a polynomial function. State the algorithm for STINGY-3 SAT, and then describe how to generalize it to STINGY-k SAT for any k. Finally, explain why this result does not contradict the fact that STINGY SAT is NP-complete.
[DVP 8.7.] Consider a special case of 3SAT in which all clauses have exactly three literals, and each variable appears at most three times. Show that this problem can be solved in polynomial time. (Hint: create a bipartite graph with clauses on the left, variables on the right, and edges whenever a variable appears in a clause. Use Exercise 7.30 to show that this graph has a matching.)
[DVP 8.21.] Sequencing by hybridization. One experimental procedure for identifying a new DNA sequence repeatedly probes it to determine which k-mers (substrings of length k) it contains. Based on these, the full sequence must then be reconstructed.
Let's now formulate this as a combinatorial problem. For any string x (the DNA sequence), let M(x) denote the multiset of all of its k-mers. In particular, M(x) contains exactly |x|-k+1 elements. (A multiset is like a set, but the same element may appear more than once.)
The reconstruction problem is now easy to state: given a multiset of k-length strings, find a string x such that M(x) is exactly this multiset.
(a) Show that the reconstruction problem reduces to Hamiltonian Path. (Hint: Construct a directed graph with one node for each k-mer, and with an edge from a to b if the last k-1 characters of a match the first k-1 characters of b.)
(b) But in fact, there is much better news. Show that the same problem also reduces to EULER PATH. (Hint: This time, use one directed edge for each k-mer.)
(c) Explain why proof (b) is relevant for determining the complexity of reconstruction, but proof (a) is not.