快速算法用于确定诱导子图是否完全

Question

我有一个无向无权图G = (V, E)，和一个随机选择的节点子集S。我想检查S中的节点是否相互邻接（即形成一个完全子图/团）。

我有以下算法（伪代码）：

foreach vertex in S  {
  // Check that the vertex has enough edges
  if (vertex.edges.count < S.size - 1)
    return false;

  // Check that there is an edge to each vertex in S
  foreach vertex2 in S  {
    if (!vertex.hasEdgeTo(vertex2))
      return false;
  }
}
return true;

问题在于这个算法的最坏情况下性能为O（|V|²）（当子集S包含完全图的所有顶点时）。

我的问题是：是否有更快的算法，其最坏情况下的复杂度更好？

- Karel Petranek

---

你是不是指的是 _O(|V|²)_？ - Svante

你可以通过仅检查每条边一次来减少常数因子。为此，内部循环应仅在外部尚未处理的所有顶点中运行。当然，这并不会提供更好的 O 复杂度。 - Svante

是的，它是O（|V|^2）而不是O（|E|^2），已经更正了。我知道我可以把时间减半，但为了清晰起见省略了。感谢您的评论。 - Karel Petranek

Answer 1

假设您可以在O(1)时间内检查两个顶点是否相交，则算法的最坏时间复杂度为O(|V|²) = O(|E|)。我认为您无法做得比O(|E|)更好，因为您应该真正检查子图的所有边。

- Bolo

---

我曾经想过，希望能找到一个好的技巧，使得时间复杂度可以达到O（|V| log（|V|）），但看来我只能坚持使用现有的方法了。 - Karel Petranek

@dark_charlie 嗯，虽然你可能无法打败 O（|S|²） 的最坏时间复杂度，但你仍然可以使用许多技巧来加快算法的平均运行时间。一个想到的方法是：以最有可能失败的问题为先的顺序询问 x.hasEdgeTo(y)。例如，您可以按照它们的度数按升序排序节点（在O（|S| log |S|）中），并按该顺序执行外部循环。 - Bolo

Answer 2

我不相信你能获得一个O(|E|^2)以外的算法来执行这个检查。逻辑上，每个V1-V2边必须被寻找来证明完整性。将其分成两个循环，第一个检查边数，第二个则检查顶点连接，可能会加快算法速度。也许用边而不是顶点来表示图形的另一种方式会有帮助？

- Will A

---

你认为使用边列表/集来表示这个问题的图有什么优势？我没有使用过这种表示方法的经验。 - Karel Petranek

Answer 3

你的hasEdgeTo函数是如何执行的？如果使用基于树的集合来存储边，那么该函数不仅仅是O(1)。

通过使用位向量来表示边，你可以达到O(|S| * min(|E|, |V|, |S|))的复杂度。

- Albert

---

hasEdgeTo是O(1)，我正在使用邻接矩阵。你对O（|S| * min(log（|E|），|S|））算法有什么想法？ - Karel Petranek

@dark_charlie：抱歉，要么我不记得昨天的想法了，要么那是胡说八道。位向量的长度将是|E|或|V|（实际上，除以8，因为你使用的是位）。但我仍在思考是否可能有另一种表示方式可以使其更快。如果我有想法或者再次记起来，我会回复的。 :) - Albert