Быстрый алгоритм определения того, завершен ли индуцированный подграф

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 содержит все вершины полного графа).

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

Answer 1

Предполагая, что вы можете проверить, совпадают ли две вершины в O(1), ваш алгоритм имеет O(|V|²) = O(|E|) сложность времени в худшем случае. Я не думаю, что вы можете сделать лучше, чем O(|E|), так как вы должны действительно проверить все края подграфа.

Answer 2

Как работает hasEdgeTo? Если вы используете древовидный набор для хранения ребер, эта функция - не просто O (1).

Используя битовый вектор для ребер, вы можете использовать O (| S | * min (| E |, | V |, | S |)).

Answer 3

Я не верю, что вы получите не O (| E | ^ 2) алгоритм для выполнения этой проверки.Логически, каждое ребро V1-V2 должно быть найдено для доказательства полноты.Разделение на два цикла, первое из которых проверяет число ребер, а второе, а затем проверка вершинных соединений, потенциально ускорит алгоритм.Возможно, поможет другой способ представления графа (с ребрами, а не с вершинами)?