```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.
```