Set packing

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

題目描述

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

形式化的定義:給定全集 ,和 的一組子集 packing指一個集合 滿足  中任意兩個集合互不相交。定義 packing的大小。

對於 set packing 的決定性問題,輸入是   對和一個整數  ,求是否存在一個大小至少為 的 packing 。對於 set packing 的最優性問題,輸入是   對,求最大的 packing 。