In all the following questions, show that they are NPC Given a graph G(V,E) and

Question

In all the following questions, show that they are NPC Given a graph G(V,E) and a number k and two different vertices a, b. Can you find a simple path from a to b of length at least k? (a path is simple if every vertex appears in the path at most once). Hint: what value of k will make it a known problem? Given a graph (G, V, E), a number k and a number b, is there a set V' of size |V'| = k so that the number of edges that have both endpoints in V' is at least b? Hint: what value of b will make it a known problem? The Knapsack problem has as input a collection of items {l,...,n} and two numbers P and B. Each item has a price pi and a volume voli. The question is: is there a subset of items S of sum of volumes at most B and sum of prices at least P? Remember that the subset sum problem is NPC and show that the Knapsack problem is NPC Hint: The volumes and the profits have to be related.

Explanation / Answer

The first problem is wrong. its clearly in P. Just find the shortest path from a to b using any shortest path algo, say dijkstra / floyd warshal. Then just verify if the length of the path is

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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