11.13

(a) A cover of total size 6.
Pick the two 3-element sets
  A = {1,2,3}  and  B = {3,4,5}.
Their union is U = {1,2,3,4,5}, so they cover the universe and
  |A| + |B| = 3 + 3 = 6.

No cover of total size 5 exists.
• Every set in C has cardinality 3.
• Using only one set we would cover at most 3 elements (|U| = 5), so ≥2 sets are required.
• With two 3-element sets the sum of sizes is already 6.
• Any solution with three or more sets costs ≥9.
Hence 6 is the minimum and 5 is impossible: however we choose two 3-element sets, at least one element is repeated (e.g. the element 3 above), so we pay 6 although only 5 distinct elements have to be covered.

(b) NP-hardness.
We reduce from the classical d-Set Cover problem, which is NP-complete even when every subset has the same fixed size d (take d=3 to obtain 3-Set Cover).

Reduction:
Given an instance (U, C, k) of d-Set Cover, construct the identical instance (U, C, K) of Minimum-Element-Set-Cover with
  K := k·d.

Correctness:
• If the original instance has ≤k sets whose union is U, their total size is k·d = K, so the new instance is a YES-instance.
• Conversely, suppose there is a sub-collection S⊆C that covers U and whose total size ≤K. Because every set has size exactly d, |S|·d ≤ K = k·d ⇒ |S| ≤ k, so the same S is a valid solution to the d-Set Cover instance.

The transformation is clearly polynomial, and feasibility is preserved in both directions; therefore Minimum-Element-Set-Cover is at least as hard as d-Set Cover and is NP-hard. □

Back to Chapter 11