空白演示
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 x\in X and the total cost sum of the edges e\in 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 x\in 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,\bar{x}_1,…,x_n,\bar{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 (\bar{x}_i) and u_i. In addition, we have an edge with cost 1 between x_i (\bar{x}_i) and c_j if clause c_j contains the literal x_i (\bar{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 x\in 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.