# 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 a1,...,an, and a target number A. The decision problem is "Does there exist a subset of {a1,...,an} that adds up to exactly A?"

The Knapsack Problem is defined as follows. The input is a list of item values v1,...,vn, item weights w1,...,wn, 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 vi ≥ V, and i ∈ S wi ≤ 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.