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.