• 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. Prove that the Redundant Clubs problem is N P -Complete. (20pts)
4. Given a graph G = (V, E) with an even number of vertices independent set of size |V |/2. Prove that HALF-IS is in N P
as the input, the HALF-IS problem is to decide if G has an -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 N P -complete, which means that choosing courses is indeed a difficult thing in our life. Use a reduction from the Independent Set problem. (20pts)
• Ungraded Problems
1. The Directed Disjoint Paths Problem is defined as follows. We are given a directed graph G and k pairs of nodes (s1, t1), (s2, t2), ..., (sk, tk). The problem is to decide whether there exist node-disjoint paths P1, P2, ..., Pk so that Pi goes from si to ti. Show that Directed Disjoint Paths is NP-complete.
1 of 1 Professor: Dr. Shahriar Shamsian
