Homework #10
1. Find all satisfying truth assignments of the Boolean formula
(x1 v -x2 v x3) ^ (-x1 v x4) ^ (x2 v -x3 v -x4)
2. In the 3-COLORING problem we are given an undirected graph and asked whether
its nodes can be colored with three colors such that no two adjacent nodes
have the same color.
Show that 3-COLORING is in NP.
3. Show that the INTERIOR DECORATOR problem is NP-Complete.
The ID problem is given a graph G = (V,E) where V = {v1, .., vn}, a set of
colors C = {c1, .., cm), a set of unordered pairs of colors
P = {(c_i1, c_j2), .., c_ip, c_jp)}, a coloring of the edges of the graph
f: E -> C, and two distinguished vertices vi and vf. We say that two colors
c_i and c_j clash if the pair (c_i, c_j) is in P.
The ID problem is to find a path in G that starts in vertex vi and ends in
vertex vf such that the colors of any two edges in the path do not clash.
ID = {,C,P,f,vi,vf: G contains a path from vi to vf with no clashing
edges}
Prove that ID is NP-Complete by showing that ID is in NP and constructing
a polynomial-time reduction from 3SAT to ID.
4. Prove that IS is NP-Complete
The INDEPENDENT SET problem is given a graph G = (V,E), find the largest
subset V' <= V such that forall u,v in V', (u,v) not in E.
IS = {, k}: there exists a subset V' of V with size |V'|>=k and
forall u,v in V', (u,v) not in E}
Example: If G = ({A,B,C,D,E,F,G}, {(A,B), (A,C), (A,D), (B,C), (B,D),
(C,G), (D,E), (D,F), (D,G), (F,G)},
then if k = 1 an IS = {A}
k = 2 IS = {A, F}
k = 3 IS = {A, E, F}
Hint: use the fact that VERTEX COVER is a known NP-Complete problem.