CS计算机代考程序代写 空白演示

空白演示

Practice Exam 2
NP-complete problem
Mengxiao Zhang

Problem description

X

Q1
Phrase the above optimization problem as a decision problem and show that it belongs to NP.
Answer:
Given an integer k, whether there exists a subset of edges E’subseteq E and a subset of nodes V’subseteq V, such that the graph G’=(V’,E’) contains a path from s to x for each xin X and the total cost sum of the edges ein E’ is no more than k.
It is in NP because given a subset of edges and nodes, we can use BFS from s to see whether s is connected to each xin X, which takes polynomial time. Also, taking a sum over all the cost of the edges and comparing it with k cost polynomial time.

Q2
Show a polynomial time construction using a reduction from 3-SAT.
Answer:
A 3-SAT instance contains n variables: x_1,…,x_n and m clauses c_1,…,c_m. Each clause contains three literals.
Construct the corresponding instance of our problem. We have:
A source node r=s
2n “literal” nodes x_1,ar{x}_1,…,x_n,ar{x}_n
m “clause” nodes c_1,…,c_m
n “variable” nodes u_1,…,u_n.
X={u_1,…,u_n,c_1,…,c_m}$,
The edge set E contains the following edges. There is an edge with cost 1 between r and each “literal” node. We also have an edge with cost 1 between x_i (ar{x}_i) and u_i. In addition, we have an edge with cost 1 between x_i (ar{x}_i) and c_j if clause c_j contains the literal x_i (ar{x}_i).

Q3
Write down the claim that the 3-SAT problem is polynomially reducible to the original problem.
Answer: 3-SAT is satisfiable if and only if the constructed graph has a subgraph that has a path from s to each xin X={u_1,…,u_n,c_1,…,c_m} of the cost not greater than k = 2n + m.

Q4
Prove the claim in the direction from 3-SAT to the reduced problem.

Q5
Prove the claim in the direction from the reduced problem to 3-SAT.