判断诱导子图是否完整的快速算法

我有一个无向无权重图G=(V,E)和一个随机选择的顶点子集S。我想检查s中的顶点是否相互相邻(即形成一个完整的子图/a组)。

我有以下算法(伪代码):

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包含完整图形的所有顶点)。

我的问题是:是否有一个更快的算法,运行时具有更好的大O最坏情况的复杂性?