Sample problems for tutorial #11

1. Graph coloring is discussed in the textbook (Section 8.7). Given a graph G=(V,E), a k-coloring of G is a function f mapping the vertices V to the integers {1,...,k}, such that f(u)≠f(v) for every edge (u,v) ∈ E.

   The 3-Coloring decision problem is "Given a graph G, does G have a 3-coloring?" The 4-Coloring decision problem is "Given a graph G, does G have a 4-coloring?"

   1. Prove that the 4-Coloring problem is in NP.
   2. The 3-Coloring problem is known to be NP complete. (This is proven in Section 8.7 of the textbook.) Prove that the 4-Coloring problem is NP complete.
2. The Subset Sum Problem is defined as follows. (See Sections 6.4 and 8.8 of the textbook.) The input is a list of numbers a₁,...,a_n, and a target number A. The decision problem is "Does there exist a subset of {a₁,...,a_n} that adds up to exactly A?"

   The Knapsack Problem is defined as follows. The input is a list of item values v₁,...,v_n, item weights w₁,...,w_n, a target value V, and a maximum capacity W. The decision problem is "Does there exist a subset S of {1,...,n} for which ∑_{i ∈ S} v_i ≥ V, and ∑_{i ∈ S} w_i ≤ W?"

   1. Prove that the Knapsack Problem is in NP.
   2. The Subset Sum problem is proven to be NP-complete in Section 8.8 of the textbook. Prove that the Knapsack Problem is NP-complete.