证明稠密子图问题通过泛化是NP完全问题

---

即使有无限的时间，算法也无法解决所有计算机问题。NP完全问题的答案仍然未知。值得注意的是，如果能够在多项式时间内解决单个NP完全问题，那么所有其他问题也可以得到解决。

稠密子图

在图论和计算机科学中，稠密子图是指每个顶点都有很多边的子图。

团

团是一个图的子图，其中每个顶点都与其他每个顶点相连，使得“子图”成为一个完全图。

“最大团问题”的目标是在给定的图G中找到最大的团，即G的一个子图，它具有最多的节点。这主要是一个“优化”问题。

类似地，“团判定问题”旨在确定在所讨论的图中是否可以找到大小为K的团。

NP完全问题

NP集合中最难的问题是NP完全问题。当且仅当满足以下条件时，判定问题L才是NP完全的：

• L属于NP（任何给定的NP完全问题的答案都可以快速验证，但没有已知的有效解）。

• 在多项式时间内，所有NP问题都可以规约到L。

证明稠密子图问题通过泛化是NP完全问题

我们将证明稠密子图问题是已知NP完全问题的泛化，以建立稠密子图问题的NP完全性。在本例中，我们将使用众所周知的团问题作为NP完全基准，如下面的“证明团问题是NP完全问题”中所示，我们需要证明从团问题到稠密子图问题的规约。

为了证明一个问题是NP完全的，我们必须证明该问题属于NP类和NP难类。（因为NP完全问题是NP难问题，同时也是NP问题）

“团判定问题”属于NP类

如果一个问题属于“NP类”，它必须具有“多项式时间”验证性，这意味着如果提供一个“证书”，则需要能够在多项式时间内检查它是否是该问题的解。

证明

证书 - 假设证书是一个团节点集S，S表示G的“子图”。

验证解包括确定图中是否存在大小为k的团。因此，确定S中顶点的总数是否满足k需要“O(1)时间”。确定每个顶点是否具有(k-1)的出度需要O(k²)时间。因为在完全图中，每个顶点都通过一条边与所有其他顶点相连。因此，完全图中的边总数为“kC2 = k*(k-1)/2)”。因此，确定由S中的k个顶点生成的图是否是完全图需要“O(k²) = O(n²)”时间（特别是当“k<=n”时，其中n是图中节点的数量）。

因此，“团判定问题”可以在“多项式时间”内验证。因此，它属于“NP类”。

>

“团判定问题”是一个“NP难”问题

如果所有NP问题都在多项式时间内规约到L，那么问题L就是NP难的。现在考虑Q的团判定问题。为了证明Q属于NP难，应该选择一个现有的NP难问题，例如P，并将该问题规约到Q的一个特定情况。如果这种规约需要多项式时间，那么Q也是一个NP难问题。根据库克定理，“布尔可满足性问题”（S）是一个NP完全问题。因此，所有NP问题都可以在多项式时间内规约到S。“如果S可以在多项式时间内规约到P，那么所有NP问题都可以在多项式时间内规约到P”，这证明了Q的多项式时间可规约性。

布尔可满足性问题可以规约到团判定问题的证明

令“E = (y1 v y2) ^ (y1' v y2') ^ (y1 v y3)”是布尔表达式，其中y1、y2和y3表示变量，“^”表示逻辑“与”，“v”表示逻辑“或”，y'表示“y的补”。令每个括号内的语句是一个子句。因此，我们有三个子句：P1、P2和P3。假设节点为 –“; ; ; ; ; ”，其中每个节点的第二个项指定它们所属的子句编号。必须连接节点，以便 -

• 属于同一子句的顶点之间没有连接。

• 任何变量与其补之间没有连接。

因此，根据以下方式组装“图G(V, E)” - {“ | a ∈ Ci} 和 E = {(, ) | i ≠ j; b ≠ a' "}。考虑具有节点; ; 的G子图。它形成一个大小为3的团。因此，赋值 – “ = <0, 1, 1>”使E成立。因此，如果可满足性表达式中有k个子句，则必须获得一个大小为k的“最大团”，并且可满足性表达式对于相关的赋值为真。因此，对于一个特定情况，可满足性问题简化为团判定问题。

输入转换

必须将团问题的输入转换为稠密子图问题的输入。

团问题的输入是一个整数k和一个无向图G(V, E)。

稠密子图问题的输入是一个无向图G'(V, E)以及一对整数p和q。

我们将以这样的方式将团问题的输入数据转换为稠密子图问题的输入数据：

p = k b = (k * (k - 1))/2 G' = G(V, E) p = k q = (k * (k - 1))/2

这种转换需要O(1)时间，因此是多项式时间的。

输出转换

必须将稠密图问题的解转换为团问题的解。

由于k = a，稠密图问题的解产生一个集合a，它是一个大小为k的团。因此，团问题可以直接使用稠密图问题的输出。因为不需要转换，所以它是多项式时间的。

正确性

输入值b的范围被限制为(k²)等于(k * (k - 1))/2。

现在我们正在寻找一个具有k个节点和至少(k * (k - 1))/2条边的子图。

因为完全图中的n个顶点最多可以包含(n * (n - 1))/2条边，所以我们可以说我们的任务是找到一个具有恰好(k * (k - 1))/2条边的k个节点的子图，这意味着结果图必须在每对顶点之间都有一条边，这只不过是一个k个顶点的团。

同样，图G(V, E)上具有k个顶点的团必须包含(k * (k - 1))/2条边，这意味着它只不过是图G(V, E)的稠密子图。

因此，这证明了团问题和稠密子图问题都有解。

稠密子图也是NP完全的，因为整个规约需要多项式时间。而且，团问题是NP完全的。

结论

NP完全性的概念与判定问题有关。之所以这样设计，是因为比较判定问题的复杂性比比较优化问题的复杂性更容易。但是，能够在多项式时间内解决判定问题通常允许我们在多项式时间内解决相关的优化问题。