Choice 1 is correct: Independent-Set ≤ P Set-Packing.
Input conversion:
Given an undirected graph G = (V, E) and an integer k for the Independent-Set problem, construct a new set collection C.
For each vertex v in V, create a set S_v in C that contains all neighboring vertices of v in G.
2. Reduction rule:
An independent set of size at least k in G exists if and only if there exists a subset of C with at least k sets that are pairwise disjoint (no two sets share any elements).
Justification:
If G has an independent set I of size at least k, each vertex in I will belong to a different set in C (its own neighbor set). These sets, by definition, will be pairwise disjoint as no vertex in I is connected to other vertices in I. Therefore, we have a collection of k disjoint sets from C, satisfying the Set-Packing condition.
Conversely, if we have a subset of C with k disjoint sets, each set represents a vertex in an independent set of size k in G. Since no two sets share elements, the corresponding vertices in G cannot be connected by any edge, forming a valid independent set.
NP-completeness implication:
Since finding an independent set of size at least k can be efficiently transformed into finding k disjoint sets in C, and Set-Packing is NP-hard, it follows that Set-Packing is also NP-complete.
This reduction relies on the fact that each vertex in the original graph essentially "chooses" one of its neighbor sets, and these choices must be compatible (no overlap) to form an independent set.
The efficiency of the transformation ensures that solving the Set-Packing problem with the constructed C is equivalent to solving the original Independent-Set problem for G and k.
Therefore, by showing that any instance of Independent-Set can be efficiently converted into an equivalent instance of Set-Packing, we establish the NP-completeness of Set-Packing.