Graded Problems
Problem 1
[15 points] Given an undirected graph with positive edge weights, the BIG-HAM- CYCLE problem is to decide if it contains a Hamiltonian cycle C such that the sum of weights of edges in C is at least half of the total sum of weights of edges in the graph. Show that finding BIG-HAM-CYCLE in a graph is NP-Complete.
Problem 2
[15 points] Show that vertex cover remains NP-Complete even if the instances are restricted to graphs with only even degree vertices.
Problem 3
[15 points] Given an undirected connected graph G= (V, E) in which a certain number of tokens t(v) 1 placed on each vertex v. You will now play the following game. You pick a vertex u that contains at least two tokens, remove two tokens from u and add one token to any one of adjacent vertices. The objective of the game is to perform a sequence of moves such that you are left with exactly one token in the whole graph. You are not allowed to pick a vertex with 0 or 1 token. Prove that the problem of finding such a sequence of moves is NP-complete by reduction from Hamiltonian Path.
Ungraded Problems
Problem 1
You are given a directed graph G = (V, E) with weights we on its edges. The weights can be negative or positive. The Zero-Weight-Cycle Problem is to decide
1
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.
Problem 2
The graph five-coloring problem is stated as follows: Determine if the vertices of G can be colored using 5 colors such that no two adjacent vertices share the same color.
Prove that the five-coloring problem is NP-complete.
Hint: You can assume that graph 3-coloring is NP-complete.
2
