Set packing

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

題目描述

給定一個有限集合 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 。