Set packing

Set packing 問題是複雜性理論和組合數學中一個經典的NP完全問題，是卡普的二十一個NP-完全問題之一。

題目描述

給定一個有限集合 S 和一些 S 的子集，求問是否可以其中的 k 個子集，他們兩兩不相交。

形式化的定義：給定全集${\mathcal {U}}$，和${\mathcal {U}}$的一組子集${\mathcal {S}}$。packing指一個集合${\mathcal {C}}$滿足${\mathcal {C}}\subseteq {\mathcal {S}}$且${\mathcal {C}}$中任意兩個集合互不相交。定義$|{\mathcal {C}}|$為packing的大小。

對於 set packing 的決定性問題，輸入是 $({\mathcal {U}},{\mathcal {S}})$ 對和一個整數 $k$，求是否存在一個大小至少為$k$的 packing 。對於 set packing 的最優性問題，輸入是 $({\mathcal {U}},{\mathcal {S}})$ 對，求最大的 packing 。