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.