Алгоритм FAST для обнаружения, если вызванный подграф завершен

У меня есть неориентированный невзвешенный график G = (V, E) и случайным образом выбранное подмножество S его вершин. Я хочу проверить, взаимно ли вершины в S смежны (т.е. сформируйте полную subgraph/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|2) (в случае, если, когда подмножество S содержит все вершины полного графика).

Мой вопрос: существует ли более быстрый алгоритм, который работает с лучшей большой сложностью худшего случая O?