Set packing

Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一個NP-完全問題之一。

题目描述

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

形式化的定义：给定全集$𝒰$，和$𝒰$的一组子集$𝒮$。packing指一个集合$𝒞$满足$𝒞\subseteq 𝒮$且$𝒞$中任意两个集合互不相交。定义$|𝒞|$为packing的大小。

对于 set packing 的決定性問題，输入是 $(𝒰,𝒮)$ 对和一个整数 $k$，求是否存在一个大小至少为$k$的 packing 。对于 set packing 的最优性問題，输入是 $(𝒰,𝒮)$ 对，求最大的 packing 。