Description

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 |− , 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 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)
2 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.