1 Graded Problems
1. Prove that the following problem is in NPC: Given an undirected graph G = (V, E), determine whether there is a spanning tree whose degree is not greater than k. That is, whether there is a subgraph G′(E′, V ), E′ ⊂ E, |E′| = |V |−1, G’ is a connected graph and all its node degrees are less than or equal to k.(20pts)
2. You are given a directed graph G=(V,E) with weights on its edges e E. The weights can be negative or positive. The Zero-Weight-Cycle Problem is to decide if there is a simple cycle in G so that the sum of the edge weights on this cycle is exactly 0. Prove that this problem is NP-complete. (20pts)
3. In a certain town, there are many clubs, and every adult belongs to at least one club. The town’s people would like to simplify their social life by disbanding as many clubs as possible, but they want to make sure that afterwards everyone will still belong to at least one club.
Formally the Redundant Clubs problem has the following input and output. INPUT: List of people; list of clubs; list of members of each club; number K.
OUTPUT: Yes if there exists a set of K clubs such that, after disbanding all clubs in this set, each person still belongs to at least one club. No otherwise.
Prove that the Redundant Clubs problem is NP -Complete. (20pts)
4. Given a graph G = (V, E) with an even number of vertices as the input, the HALF-IS problem is to decide if G has an independent set of size |V |/2. Prove that HALF-IS is in NP -Complete. (20pts)
5. There are n courses at USC, each of them requires multiple disjoint time intervals. For example, a course may require the time from 9am to 11am and 2pm to 3pm and 4pm to 5pm (you can assume the number of intervals of a course is at least 1, at most n). You want to know, given a number K, if it’s possible to take at least K courses. You cannot choose any two overlapping courses. Prove that the problem is NP -complete, which means that choosing courses is indeed a difficult thing in our life. Use a reduction from the Independent Set problem. (20pts)
2 Ungraded Problems
1. Suppose we have a variation on the 3-SAT problem called Min-3-SAT, where the literals are never negated. Of course, in this case it is possible to satisfy all clauses by simply setting all literals to true. But, we are additionally given a numb er k, and are asked to determine whether we can satisfy all clauses while setting at most k literals to be true. Prove that Min -3-SAT is NP-Complete.
