Prove that the problems given in parts (a) and (b) below are NP-complete. For th

Question

Prove that the problems given in parts (a) and (b) below are NP-complete. For this purpose you can assume the NP-completeness of the following problems: CLIQUE Instance: A graph G = (V, E), a positive integer k. Question: Does G contain a k-clique? HAMILTONIAN CIRCUIT (HC) Instance: A graph G = (V, E). Question: Does G contain a cycle that visits each vertex in V exactly once? PARTITION Instance: A set S = {w1, w2, ..., wk} of positive integers, not necessarily distinct. Question: Does S contain a subset S' such that w S' w = w S-S' w? KNAPSACK Instance: A set S = {x1, x2, ..., xk} with a "weight function" w: S rightarrow Z+ and a "value function" v: S rightarrow Z+, a "weight limit" W, and a "value limit" V. Question: Does S contain a subset S' such that x s'w(x) le W; x s' v(x) ge V? SUBGRAPH ISOMORPHISM Instance: Two graphs G1 = (V1, E1), G2 = (V2, E2). Question: Does G1 contain a subgraph which is isomorphic to G2? Note: A subgraph of G = (V, E) is a graph G' = (V', E') with V' V, E' E. Two graphs G = (V, E), G' = (V', E') are said to be isomorphic if V = V' , E = E', and there exists a one-to-one mapping between the vertices, f: V rightarrow V', such that (u,v) E (f(u), f(v)) E'.

Explanation / Answer

a)The first step is to prove Knapsack is in the NP class. (This is very important, but some students forget.) Given an input set, it is very easy to check if the total weight is at most b and if the corresponding profit is at least k. It takes only linear time to add the weights and profits of all the goods to find the true/false result. The second is to prove a certain problem, which is already known to be NP-Complete, can be reduced to Knapsack problem in polynomial time. We can choose any of the NP-Complete problem we have learned. Because we already know all the problems in the NP class can be reduced to the chosen problem, say Subset Sum, we know all these problems can also be reduced to Knapsack problem. It is very easy to reduce an instance of Subset Sum problem to an instance of Knapsack problem. We just create such a Knapsack problem that

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.