最常见的大小为k的子集

Question

假设您有一个S1,...,Sn整数范围的子集列表R={1,2,...,N}和一个整数k.有没有找到一个子集的有效途径C的R大小k,从而C是的最大的一个子集Si？

举个例子,让R={1,2,3,4}和k=2

S1={1,2,3}
S2={1,2,3}
S3={1,2,4}
S4={1,3,4}

然后我想要返回C={1,2}或C={1,3}(并不重要).

Answer 1

我认为你的问题是NP-Hard。考虑二部图，其中左侧节点是集合，右侧节点是整数{1, ..., N}，如果集合包含整数，则两个节点之间有一条边。然后，找到大小 的公共子集k，它是 的最大数量的子集Si，相当于找到K(i, k)具有最大边数 的完全二分子图i*k。如果您可以在多项式时间内完成此操作，那么您可以通过尝试每个固定 来找到在多项式时间内K(i, j)具有最大边数的完整二分子图。但是这个问题是NP-Complete（完全二分图）。i*jk

因此，除非 P=NP，否则您的问题没有多项式时间算法。