问题标签 [clique-problem]

我正在研究 NP 课程，其中一张幻灯片提到：

是否曾经证明，CLIQUE 的补语是否是 NP 的一个元素？

另外，你有证据吗？

如何列出无向图的所有派系？（并非所有最大派系，如 Bron-Kerbosch 算法）

维基百科上显示的图形模型中的最大集团 仅包括大小为 3 和 4 的集团。但我认为根据上述定义，2 号规模的集团（连接 3,4 号规模的集团）也应包含在最大集团中。如果我错了，任何人都可以纠正我。

我已经搜索了很长时间，但我无法意识到找到 clique percolation 的最佳方法是什么。如我所见，有两种方法

1. 在图 G 中找到大小为 k 的团，然后在相邻的团节点之间创建一个图。
2. 找到大小 >= k-1 的最大派系，然后在相邻派系节点之间创建一个图。

好吧，我知道找到 max-cliques 是 NP-Complete 问题，并且据我所知，在图 G 中找到 k clique 是多项式，那么第一种方法是否更有效？如果有人可以帮助并澄清问题，我会很高兴，谢谢。

我正在尝试编写一种算法来计算输入图（无向且无自环）的边缘团覆盖数（覆盖所有边缘的最小团数）。我的想法是

1. 使用Bron-Kerbosch算法计算所有最大团，以及
2. 尝试其中任何 1,2,3,... 是否会覆盖所有边缘，直到我找到最小数量

那行得通吗？有人知道更好的方法吗？有标准算法吗？令我惊讶的是，我找不到任何这样的算法。我知道这个问题是 NP 难的，所以我不希望有一个快速的解决方案。

给定一个基于如下图的数据结构：

其中键表示其上包含的向量的大小。

一开始，地图只有一个键（例如[3]），其中包含输入向量（例如{1, 3, 5}和{2, 4, 6}）。

我的函数获取存储在地图最大键中的向量，并将它们分解为具有较少元素的所有可能组合，并将它们存储在与新向量的大小相对应的键中（例如）。[2] = {1,3} {1,5} {3,5} {2,4} {2,6} {4,6} and [1] = {1} {3} {5} {2} {4} {6}

我不知道我的解决方案是否最有效，但效果很好。但是由于我的项目旨在处理大量数据，因此我需要并行化我的代码，这导致我进行了以下实现：

使用“omp parallel”和“omp single”（而不是“omp for”）允许安全地访问数据结构，同时允许所有其他操作并行运行。该代码几乎可以完美运行，几乎...因为它在最终结果中遗漏了一些（很少）子向量（如果禁用 omp 则成功生成）。

是否有任何“OMP 专家”能够帮助我解决这个问题？先感谢您。

---------------

更新

最小完整可验证示例

我想在给定 n 行的情况下创建一个邻接矩阵，这些行表示图的某些节点之间的部分连接。例如，由于每条线代表一个集团，这些线A-B; B-C; C-D; A-E-D形成下图。

我的第一种方法是使用 afor loop读取每一行，对于每一行，我使用另一个for loop来获取其中的每个节点，最后，for loop我检查其余节点是否已经在分析的节点的 adyacence 列表中，如果没有，我添加它。所有这些都给出了 O(n^3) 的复杂度。是否有另一种方法可以降低复杂性？是否有可能用 O(n) 完成？

我有以下问题：给定一组男性和一组女性，任何两个人之间的等级等于 0 或 1。选择一个人的子集，这样：

• 我想最大化被喜欢的人的数量（子集中任何两个人之间所有等级的总和）超过子集中的总人数。

• 在挑选出来的人群中，男性和女性的数量必须相等。

我的问题是：为了显示这个问题的 np 完整性，我知道可以使用 clique 问题减少......有没有人可以提供一个关于如何进行这种减少的例子？我需要减少 FROM 或 TO 集团问题吗？非常感谢

我目前正在尝试制作一种算法来查找图中的派系，幸运的是，我从 Networkx 找到了一个可以做到这一点的函数的文档。不幸的是，变量名称有点简洁，我无法理解代码的每个部分的作用。

这是 find_cliques 的代码：

它工作得很好，但我只是想了解这里发生了什么，我似乎无法在网上找到任何解释它的资源。

我很惊讶networkx似乎没有内置函数来做到这一点，但也许我错过了一些使用内置算法来做到这一点的聪明方法？