在一个图中找到所有完整的子图

Question

是否存在已知的算法或方法可以在图中找到所有完整子图？我有一个无向、无权图，需要找到其中所有子图，其中子图中的每个节点都与子图中的其他节点相连。

是否有现成的算法可用于此项任务？

- Mantas Vidutis

---

@bummi 你在开玩笑吧？StackOverflow 最初就是为算法设计问题而建立的，软件算法是“我可以询问的事情”中涵盖的第二个主题。http://stackoverflow.com/help/on-topic - Mantas Vidutis

Answer 1

这被称为团问题；它通常是NP完全的，并且有许多算法可以解决这个问题。

如果图具有其他属性（例如，它是二分图），那么问题会变得相对容易，并且可以在多项式时间内解决，但否则很难，并且仅适用于小型图。

来源：维基百科

在计算机科学中，团问题指与在图中查找特定的完全子图（“团”）相关的问题，即每对元素都连接的元素集合。

团问题包括：

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

这些问题都很难：团决策问题是NP完全的（Karp的21个NP完全问题之一），查找最大团问题既是固定参数难以处理又难以近似，列出所有极大团可能需要指数时间，因为存在具有指数数量的极大团的图。尽管如此，对于这些问题有运行在指数时间内或处理某些更专业输入图的算法可以解决。

另请参见

• Bron-Kerbosch算法

- polygenelubricants

---

我们在家观看的观众应该注意，本文的完整文本位于ACM会员墙后面。 - Mantas Vidutis

你好，NP-hard是指没有能够在多项式时间内运行的算法吗？ - SexyBeast

是的，NP-Hard意味着没有算法可以在渐近多项式时间内解决这个问题。更重要的是，它意味着算法的正确性也不能在多项式时间内进行检查。 - divanshu

吹毛求疵：这不是团问题。虽然与之相关，且至少和团问题一样难，但它不是同一个问题。该问题要求找到所有的团。而团问题是指测试是否存在某个特定大小（大致上）的团，这是不同的。因此，该问题不属于NP（它不是决策问题），也不是NP完全问题。尽管如此，它仍然是NP难问题。 - D.W.

Answer 2

在大小为n的图中找到一个k-顶点子图的问题的复杂度为

O(n^k k^2)

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

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

- Pradeep Banavara

---

挑剔一点：找到所有的团并不是NP完全问题。它不是一个决策问题，因此不属于NP。但它是NP难问题。 - D.W.