Discussion 10
1. Given the SAT problem from lecture for a Boolean expression in Conjunctive Normal Form
with any number of clauses and any number of literals in each clause. For example, (X1 X3)(X1 X2 X4 X5)…
Prove that SAT is polynomial time reducible to the 3-SAT problem (in which each clause contains at most 3 literals.)
Copyright By PowCoder代写 加微信 powcoder
Solution: We will turn each clause of size k in the SAT problem into one or more clauses of size 3 as follows:
—————-
(X1 X2X3)
(X1 X2X3X4)
(X1 X2X3X4X5)
———————-
(X1 X1 X1)
(X1 X2X1)
(X1 X2X3)
(X1 X2S1)(S1 X3X4)
(X1 X2S1)(S1 X3S2)(S2 X4X5)
Clause size —————- 1
In general, we
variables to “chain” the clauses together using conjunction as shown in above examples.
Proof: We need to show that the clause of size k is satisfiable iff the chain of clauses of size 3 is satisfiable. To show this:
A – if we have a satisfying truth assignment in the clause of size k, we can find a satisfying truth assignment in the chain of clauses of size 3, because the satisfying truth assignment in the clause of size k requires at least one of the terms in the clause to be true. This will cause one of the (k-2) clauses of size 3 in the chain to evaluate to 1, we can then use the k-3 dummy variables to set the remaining clauses to be true and therefore find a satisfying truth assignment for the chain.
B – if we have a satisfying truth assignment in the chain of clauses of size 3, it must be that at least one of the Xi variables is true (because the dummy variables on their own can only set k-3 clauses to true). And a satisfying truth assignment in the clause of size k requires only one of the Xi variable to be true. So this will be a satisfying truth assignment.
can turn any clause of size k>3 into k-2 clauses of size 3 using k-3 dummy
2. The Set Packing problem is as follows. We are given m sets S1, S2, … Sm and an integer k. Our goal is to select k of the m sets such that no selected pair have any elements in common. Prove that this problem is NP-complete.
1- Prove that Set Packing is in NP
Certificate: a subset of k sets (out of the m sets given) that have no elements in common Certifier: Can easily check in polynomial time that
a- There are k sets in the certificate
b- The k sets have no elements in common
A and b can be easily done in polynomial time. Set Packing ε NP
2- Choose independent set for our reduction
3- Will show that Indep. Set ≤p Set Packing
We will start with an instance of the Indep Set problem (Is there an indep set of size at least k in G) and will construct a set of sets such that there are k of them that have no elements in common iff we have an independent set of size k in G.
Construction of sets: For each node i in G we will create a set Si . The elements of Si will consist of the edges incident on i in G.
Proof of correctness for the reduction step:
A – If we have an indep set of size k in G, we can use that to find k sets that have no common elements. The reason is that since the k nodes in G are independent they do not share any edges, therefore the sets corresponding to these k nodes will not have any elements in common since these elements correspond to the edges incident on the k nodes in G.
B – If we have k sets that have no elements in common, we can find an indep set of size k in G. The reason is that since these sets do not have any elements in common, the corresponding nodes in G will have no edges in common or in other words they will be independent, and will form an indep set of size k.
3. The problem is as follows. Given an undirected graph G=(V,E) with nonnegative edge costs and whose vertices are partitioned into two sets, R and S, find a tree T ⊆ G such that for every v in R, v is in T with total cost at most C. That is, the tree that contains every vertex in R (and possibly some in S) with a total edge cost of at most C.
Prove that this problem is NP-complete.
1- Prove that the Problem is in NP
Certificate: a tree of cost at most C that covers all nodes in R Certifier: Can easily check in polynomial time that
a- Tree covers on nodes in R (run BFS on the tree)
b- The total cost of the tree is at most C
A and b can be easily done in polynomial time. Problem ε NP
2- Choose vertex cover for our reduction
3- Will show that Vertex Cover ≤p Problem
We will start with an instance of the vertex cover problem (Is there an vertex cover of size at most k in G) and will construct G’ such that G has a vertex cover of size at most k iff G’ has a of cost at most m+k.
Construction of G’: G’ will have the same set of nodes and edges in G plus a number of new nodes and edges. The nodes in G’ that exist in G will belong to the set S. We now introduce a new set of nodes in G’:
– We will add one node (re) per edge e in G’ (adding m nodes in this process). All these nodes will belong to the set R
– We will connect each node to the two ends of the corresponding edge in G’
– Wewilladdonemorenoder0 inG’andwillconnectr0 toallthenodesinthesetSinG’
– AlledgesinG’willhaveacostof1
Proof of correctness for the reduction step:
A- IfwehaveavertexcoverofsizekinG,wecanproduceaSteinertreeofcostm+kinG’.
This can be done by using the following edges in the
a. k edges that connect r0 to the node in G’ corresponding to those k nodes that
form a vertex cover of size k in G.
b. m edges that connect each of the re nodes in G’ to the node that covers in e in G.
This will result in a tree of cost m+k that covers all nodes in the set R.
B- IfwehaveaSteinertreeofcostm+kinG’wecanproduceavertexcoverofsizekinG. This can be done by putting all the nodes in the set S that are part of the Steiner tree in the vertex cover set. (m of the edges will be needed to connect re nodes to one of the S nodes. The other k edges in the tree will be connecting these S nodes (that are part of the tree) to other S nodes on the tree (for example through node r0 ). Since these S nodes have direct connections to all nodes in the set R, then the nodes corresponding to these S nodes in G will form a vertex cover of size k.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com