Set packing

给定一个有限集合 S 和一些 S 的子集，求问是否可以其中的 k 个子集，他们两两不相交。

形式化的定义：给定全集${\displaystyle {\mathcal {U}}}$ ，和${\displaystyle {\mathcal {U}}}$ 的一组子集${\displaystyle {\mathcal {S}}}$ 。packing指一个集合${\displaystyle {\mathcal {C}}}$ 满足${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$ 且${\displaystyle {\mathcal {C}}}$ 中任意两个集合互不相交。定义${\displaystyle |{\mathcal {C}}|}$ 为packing的大小。

对于 set packing 的决定性问题，输入是 ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$  对和一个整数 ${\displaystyle k}$ ，求是否存在一个大小至少为${\displaystyle k}$ 的 packing 。对于 set packing 的最优性问题，输入是 ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$  对，求最大的 packing 。