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 。