11.11

Reduction.
Given an instance of Vertex-Cover, a graph [math]G=(V,E)[/math] and an integer [math]k[/math], build a baseball-card instance as follows.

1. “Cards’’ = the edges: [math]C:=E[/math].
2. For every vertex [math]v\in V[/math] create one packet
    P_v := \{\,e\in E\;|\;e\text{ is incident to }v\,\}.
3. Keep the same bound [math]k[/math].

Correctness.
• (⇐) If [math]S\subseteq V[/math] is a vertex cover of size ≤ [math]k[/math], pick the packets whose names are the vertices in [math]S[/math]. Every edge is incident to some vertex of [math]S[/math], hence every card appears in a chosen packet, so all cards are collected with ≤ [math]k[/math] packets.
• (⇒) If ≤ [math]k[/math] packets suffice to obtain all cards, let [math]S[/math] be the corresponding vertices. Because every card (edge) is contained in at least one selected packet, every edge has an endpoint in [math]S[/math]; thus [math]S[/math] is a vertex cover of size ≤ [math]k[/math].

Complexity. The construction creates |V| packets and lists each edge twice, so it runs in time polynomial in |V|+|E|.

Because the transformation is polynomial and the two solutions correspond one-to-one, the baseball card collector problem is at least as hard as Vertex-Cover; hence it is NP-hard.

Back to Chapter 11