A set of Pokemon cards consists of n different cards. The cards are sold as diff
ID: 3867978 • Letter: A
Question
A set of Pokemon cards consists of n different cards. The cards are sold as different sized
randomly selected packs. Each pack is a subset of the set of Pokemon cards. There arem such
packs. You happen to know which cards were placed in which packs. You want to select a
minimum set of packs such that you will get at least one of every every card in the set.
1. Show this problem is in NP.
2. Give a verification algorithmfor this problem.
3. Prove your algorithm is correct.
4. The Vertex Cover problem is already known to be NP-complete. We can show that
Pokemon is NP-complete by reducing Vertex Cover to Pokemon.
a) Give a reduction from Vertex Cover to Pokemon. The reduction takes
input to Vertex Cover and converts it into input to Pokemon.
b) Prove your reduction is correct.
Explanation / Answer
Answer:
1. The given problem is a Non-deterministic one as the outcome (atlast one desired card in each set) depends on number of possibilities (on selected sets, say k, out of m). Now it is possible to decide in polynomial time whether at least one desired card exists in every selected set. Hence, this problem is in NP.
2. Verification algorithm: See below:
-------------------------------------------
We assume that set k exists. A set p of desired cards also exists. Then, given k, m and p, our algoritm will answer in "YES" or "NO":
For all selected set in k out of m,
if a desired card from p is in selected set, answer "YES".
else if a desired card from p is not in selected set, answer "NO".
--------------------------------
3. Correctness: An algorithm is termed correct if it terminates gracefully with desired outcome. Verification algoritm given above will terminate with a YES/NO answer for all selected sets in definite time. Hence, this algorithm is correct.
4.
a) Reduction from Vertex cover to Pokemon card problem: It is required to prove:
Objective: Vertex cover is reducible to Pokemon card
Strategy:
1. Vertex cover is a subset of vetices in an undirected graph G that covers all the edges in graph. We know that it is a NP-Complete problem.
2. We can formulate Pokemon Card problem as a graph problem by visualising a graph G such that various possible sets (total number m) are vertices in G such that |V| = m and (u,v) in E for any u,v in V iff a desired card is present between u and v.
3. Now vertex cover problem can be applied on this graph to find vertices that cover all edges in graph and a solution, if found, will be the solution to Pokemon Card problem.
4. Hence, Vertex-Cover problem is reducible to Pokemon Card problem.
b) Correctness of reducton:
It can be shown that:
a) A solution to vertex cover problem is a solution to pokemon card problem and
b) A solution to pokemon card problem is a solution to vertex cover problem.
Hence this reduction is correct.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.