跳至內容

Set packing

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

題目描述

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

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

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