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)

    Solution:

    x1 = T

       x4 ^ (x2 v -x3 v -x4)
       x4 must be T

	  (x2 v -x3)
	  x2 = T

	     T
	     x3 = T or F

	  x2 = F
	     -x3
	     x3 must be F

    x1 = F

       (-x2 v x3) ^ (x2 v -x3 v -x4)
       x2 = T

	  x3
	  x3 must be T

	     T
	     x4 = T or F

       x2 = F

	  (-x3 v -x4)
	  x3 = T

	     -x4
	     x4 must be F

	  x3 = F

	     T
	     x4 = T or F

    {, ,
     ,
     , ,
     , ,
     }


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.


    Solution:

       3-COLORING = {, c1, c2, c3:  there exists a function from nodes in G
       to {c1, c2, c3} such that no two adjacent nodes have the same color.}

       An answer to the 3-COLORING problem is a function f from nodes in
       G = (V, E) to {c1, c2, c3}.  In O(|V|^2) steps we can check every
       edge (u,v) in E to make sure that f(u) is not equal to f(v).
       Thus 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.

    Solution:

       (1) ID is in NP
	   If a list of vertices (u1, .., uk) is guessed, it can be verified
	   in polynomial time.
	   Check to see if u1 = vi and uk = vf (constant time).
           For each i, check to see if (u_i, u_i+1) is in E (linear time).
	   For each i and j, i not equal to j, check to see if
	   (f(u_i, u_{i+1}), f(u_j, u_{j+1})) is not in P (colors do not clash,
	   this takes polynomial time).

       (2) 3SAT <=P ID
           Let U = (x1, .., xn) be a set of variables and let E be a 3SAT
	   expression over U with m clauses.  Each literal in clause E_i
	   is either xk or -xk for some k.

	   The set of colors is assigned to be the set of literals, and pairs of
	   (variable, -variable) are designated as clashing.  Given an
	   expression in 3SAT, a graph is constructed such that it has
	   a path with nonclashing colors from beginning to end if and only if
	   the expression is satisfiable.

	   The graph is a chain of length n+m from start vertex to end vertex so
	   that the path is forced to visit each vertex.  The first n
	   edges correspond to the n variables, while the last m edges
	   correspond to the m clauses.  Each variable edge is replaced by
	   2 chains of length 2; one colored with the variable and the other
	   colored with the complement of the variable (the reason we do not
	   just put two edges is that a graph is typically assumed not to have
	   multiple edges); and each clause edge is replaced by 3 chains of
	   length 2, each one colored with one of the literals.


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.

    Solution:

       (1)  Prove IS in NP.
	    Given a solution V' we can check in constant time if |V'| >= k
	    and can check each edge u,v in V' in time |V'|^2 that
	    (u,v) is not in E.

       (2)  VC <=P IS
            Note if G = (V,E) has a vertex cover V' then V - V' is an
	    Independent Set.

	    Thus (G,k) in VC <=> (G, |V| - k) in IS

	    If V' is a VC is V - V' an IS?
	    Note that for all edges in in E, e contains some element of V' as
	    one of its endpoints.  Thus vertices in V - V' are not endpoints for
	    any edges in E.  Thus when we connect u,v in V - V', the resulting
	    edge (u,v) cannot be in E.  Thus the vertices in V form an
	    INDEPENDENT SET.

	    If V - V' is an IS is V' a VC?
	    Note that no edge-connected vertices using edges from E can be found
	    in V - V'.  Thus all edges in E must be found either completely
	    within the graph (V', E) or one endpoint of an edge is in V' and
	    one endpoint is in V - V'.  In either case, at least one endpoint of
	    every edge in E is in V'.  Thus V' is a VC.