查找图中所有完整的子图

Question

是否有已知的算法或方法来查找图中的所有完整子图？我有一个无向、未加权的图，我需要找到其中的所有子图，其中子图中的每个节点都连接到子图中的每个其他节点。

有现成的算法吗？

Answer 1

这被称为派系问题；这很困难，而且一般来说是 NP 完全的，是的，有很多算法可以做到这一点。

如果图具有额外的属性（例如，它是二分图），那么问题就会变得相当容易，并且可以在多项式时间内解决，但否则它就非常困难，并且仅对于小图才能完全解决。

来自维基百科

在计算机科学中，派问题是指与在图中查找特定完整子图（“派”）相关的任何问题，即每对元素相连的元素集。

派系问题包括：

• 找到最大团（顶点数最多的团），
• 在加权图中找到最大权重团，
• 列出所有最大派系（无法扩大的派系）
• 解决测试图是否包含大于给定大小的团的决策问题。

这些问题都很困难：派系决策问题是 NP 完全问题（卡普的 21 个 NP 完全问题之一），寻找最大派系的问题既是固定参数棘手的又难以近似，并且列出所有最大值派系可能需要指数时间，因为存在具有指数级多个最大派系的图。然而，针对这些问题的算法可以在指数时间内运行，或者在多项式时间内处理某些更专业的输入图。

另请参阅

• Bron-Kerbosch 算法

Answer 2

在大小为 n 的图中找到 k 顶点子图的问题很复杂

O(n^kk^2)

因为有 n^k 个子图需要检查，并且每个子图都有 k^2 条边。

您所要求的，查找图中的所有子图是一个 NP 完全问题，并在上​​面列出的 Bron-Kerbosch 算法中进行了解释。