查找图中的所有完整子图

这被称为 clique problem ;这很难,而且通常是np完全的,是的,有很多算法可以做到这一点。

如果图有额外的性质(例如它是二部的),那么这个问题就变得容易得多,并且在多项式时间内是可解的,但是在其他情况下它是非常困难的,并且只对小图是完全可解的。

来自维基百科

在计算机科学中,团问题是指与在图中找到特定的完全子图(团)有关的任何问题,即每对元素连接的元素集。

集团问题包括:

• 找到最大团(顶点数最大的团)。
• 在一个加权图中找到一个最大权群,
• 列出所有最大团(不能扩大的团)
• 解决测试图是否包含大于给定大小的团的决策问题。

这些问题都是困难的:集团决策问题是np完全问题(karp的21个np完全问题之一),寻找最大集团的问题是固定参数且难以逼近的,列出所有最大集团可能需要指数时间,因为存在图。具有指数级的多个最大集团。然而,对于这些问题,有一些算法在指数时间内运行,或者在多项式时间内处理某些更特殊的输入图。

另见

• Bron–Kerbosch algorithm

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

o(n^k k^2)

既然有 n^k 要检查的子图,每个子图都有 k^2 边缘。

你所要求的是,在一个图中找到所有子图是一个np完全问题,并在上面列出的bron-kerbosch算法中解释。