algorithm - 具有集合大小约束（P 或 NP）的最大覆盖问题的问题复杂性

Question

经典的最大覆盖 (MC) 问题是一个 NP-hard 优化问题。考虑 d 个元素U = {e1, e2, ... ed}和 c 集合T1, T2 ... Tc。每个集合包含 U 中的一些元素。问题旨在找到最多b个集合，使得这些集合的并集的基数最大化。例如，T1={e1, e3}, T2={e1, e2, e3} 和 T3={e3, e4}。当 b=2 时，最优解选择 T2 和 T3。我正在考虑经典 MC 问题的变体，它施加了一个集合大小约束。考虑 1 < k <= d，如果所有集合的大小都以 k 为界。将此问题称为 k-MC。问题仍然是 NP 难的吗？

我的猜想是k-MC仍然是 NP-hard，但我正在努力从一个已证明的 NP-hard 问题（如 MC）中提出多项式约简。对于最大覆盖率的任意实例，如果我能找到对所有 k>1 的问题的多项式归约，我可以得出结论，我的问题也是 NP 难的。这是我到目前为止得到的：

1. 当 k=d 时，该问题与经典的最大覆盖率非常等价。
2. 当 k=d-1 时，我们查看给定的 MC 实例，看看是否存在大小为 d 的集合。如果有，只需选择它。否则，它会简化为 k=d-1 的k-MC问题。

当 k 小于 d-1 时，我求助于动态规划来完成归约。但是，这会产生非多项式时间缩减，这违背了从 NP 难题中缩减的目的。

如果有人能给我一些关于我应该如何解决这个问题的指示，或者甚至只是对k-MC （P 或 NP）的问题复杂性做出有根据的猜测，我将非常感激。

标签： algorithmcomplexity-theorynp

Answer 1

2-MC 很简单——将大小为 2 的集合解释为一个图，并为非二分图运行您最喜欢的匹配算法。一旦你超过了匹配的基数，你就会陷入选择单例的困境。

3-MC很难。您可以将3-partition的实例编码为 3-MC，方法是将集合作为与目标相加的三元组，然后通过检查 b = n/3 的覆盖率来确定它是否可解。