Reduce independent set problem to set packing problem

[GiggleLiu]

No description provided.

[SciCodePhy]

Reduce Independent Set Problem to Set Packing Problem

I. Definitions and Background

I-A. Independent Set Problem (IS)

See "Reduce 3-SAT to Independent SAT Problem" issue.

I-B. Set Packing Problem

• Pairwise Disjoint: For a collection of sets, any two of them don't share elements.

Input:

• An universe $U$ (need to check: whether $U$ needs to be a finite set);
• A collection of $U$'s subsests: $S={S_1, S_2, \cdots S_m }$ (aka: family);
• A collection of some of the above subsets (aka: subfamily) that is pairwise disjoint. This subfamily is called a packing, while the size of the packing is the number of subsets included.

Output:

• Whether there is a packing of size $k$.

II. Proof (IS <= Set Packing)

The reduction is as follows [Ref. 1]:

Given an undirected graph $G=(V,E)$ and $k$, we aim to generate $(U, S, k)$.

• Step-0: $k$ are the same;

• Step-1: Each edge $(u,v)\in E$ -> Create an element $x_{u,v}$ in $U$;

• Step-2: Each vertex $v \in V$ -> Create a subset ${S_{u,v}|(u,v)\in E }$.

  It can be proven that:

• $(G,k)$ is an yes-instance if and only if generated $(U,S,k)$ is an yes-instance;

• This transformation is within polynomial time.

III. References

Core References:

1. https://kgardner.people.amherst.edu/courses/f19/cosc311/mini/mini10solutions.pdf