CSCI 570  Homework 11

CSCI 570 
Homework 11
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. 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. 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