这是一个家庭作业问题。我只是在开始之前有一些问题。
我们的问题是：
“从 k 独立集减少到 2−SAT，如下所示。给定一个具有 n 个顶点的图 G 形成 n 个命题，每个顶点一个命题。如果顶点 i 属于独立集，则顶点 i 的每个命题 xi 都设置为真。现在为每条边 (u,v) 写一个子句，说 u 和 v 都不能属于独立集。”
我的问题是，我读到的所有内容都说 2-SAT 不是 NP 完全问题。那么我们怎样才能减少独立集问题呢？
问问题
1380 次
1 回答
2
找到任何独立集和找到最大独立集（最大大小的独立集）之间存在重要区别。
使用您在问题中描述的减少，找到任何独立的集合很好地减少到 2-SAT。这两个问题都不是 NP 完全的。请注意，您在问题中描述的减少不会以任何方式限制独立集中的节点数量。即使是空集也能满足这种归约产生的 2-SAT 问题，因为空集也是一个独立集！
然而，找到一个最大独立集（或 k 独立集）是一个 NP 完全问题。它不会减少到 2-SAT。
或者换句话说：“ k -Independent Set”中的k是一个额外的约束，它不是这个 2-SAT 缩减的一部分（这就是为什么在缩减的描述中甚至没有提到k的原因）。您可以在 SAT 问题中添加额外的子句来计算包含节点的数量并强制该数字至少为k，但您不能通过仅添加 2 个子句来做到这一点。因此，添加k是您的 2-SAT 问题成为 NP 完全一般 SAT 问题的步骤。
MAX-2-SAT是 2-SAT 的 NP 完全扩展，也可用于使用您发布的约简解决最大独立集问题。（您需要对归约进行两个微不足道的修改：（1）为每个命题添加 1 子句，（2）复制 2 子句以进行加权。）
于 2015-12-05T11:06:08.930 回答