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