CompSci 260P Algorithms Problem Set 2: Complexity
For purposes of CompSci 260P, when proving a problem is N P-complete, you do not need to prove it is in N P, even though the formal definition would require this. You need only give a reduction and an explanation for why it is correct; the most convenient way for the latter is by showing it produces no false positives and no false negatives. For your reduction, you may use any problem shown in lecture or lab to be N P-complete. If it is not obvious that your reduction is polynomial time, you would need to explain why it is; most questions I plan to give in 260P will fit this description.
1. The following is a version of the Independent Set Problem. You are given a graph G = (V, E) and an integer k. For this problem, we will call a set I ⊂ V strongly independent if, for any two nodes v, u ∈ I, the edge (v, u) does not belong to E, and there is also no path of two edges from u to v; that is, there is no node w such that both (u, w) ∈ E and (w, v) ∈ E. The Strongly Independent Set problem is to decide whether or not G has a strongly independent set of size at least k. Prove that Strongly Independent Set is N P-complete.
2. The Set Packing problem is as follows. We are given n sets S1, S2, . . . Sn and an integer k. Our goal is to select k of the n sets such that no selected pair have any elements in common. Prove that this problem is N P-complete.
3. The Stingy-Sat problem has input that looks like an instance of the 3-Sat problem, but the literals are never negated. It is possible to satisfy all clauses by simply setting all literals to true. We are additionally given a number k, and are asked to determine whether we can satisfy all clauses while setting at most k literals to be true. Prove that this problem is N P-complete.
4. In the Clustering problem, we are given a weighted graph G = (V, E), an integer k, and a target T. We want to divide the vertices into k sets such that any pair of nodes in the same set have a shortest path of length ≤ T to every other vertex in that set. Prove that Clustering is N P-complete.
5. A Tonian Path in a directed graph is a simple path (no vertices are repeated) that includes at least half (≥ n/2) of the vertices. Show that the problem of determining if a graph has a Tonian Path is N P-complete.
6. In the Min-Cost Fast Path problem, we are given a graph G = (V, E) along with nonnegative integer times t(e) and non-negative costs c(e) on each edge. Our goal is to determine if there is a path P from s to t such that P e∈P t(e) ≤ T and also that P e∈P c(e) ≤ C, for some given integers T and C. Prove that this problem is N P-complete. If you are looking for additional practice questions, I recommend the following problems from the course textbooks.
If you are using the textbook of Goodrich and Tamassia, try C-17.9, C-17.11, C17.12, and A-17.1 through A-17.7. If you are using the textbook of Erickson, I recommend Chapter 12, problems 8, 9, 10, 22 (a and b), 25, 28a, 29, 30, 31, 32, 36, 37, 39.