| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
The vertex cover problem (described below) is known to be NP-complete. Prove that the card collector problem (also described below) is also NP-complete using a reduction. Keep in mind that you need to show that the card collector problem is in NP as well as giving the reduction itself. Also explain why the reduction is correct — you'll get the right answer to the problem — and polynomial-time.
Vertex cover problem: Given a graph G and a positive integer k, is there a vertex cover of G with size at most k? A vertex cover of a graph G is a set of vertices such that every edge of G has at least one endpoint in the set.
Card collector problem: Given n packets of cards (each of which contains a subset of the available cards) and a positive integer k, is it possible to collect the full set of cards by buying no more than k packets? For example, if there are four cards available (A, B, C, D) and the packets contain {A,B}, {B,C}, {D}, {B,D}, then the answer is no for k=2 (packet 1 is needed for card A, packet 2 is needed for card C, and either packet 3 or 4 is needed for card D) and yes for k=3 (e.g. packets {A,B}, {B,C}, {D} result in the full set).