[SOLVED] 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 Esubseteq E and a subset of nodes Vsubseteq 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,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 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 claimin the direction from the reduced problem to 3-SAT.