Fast algorithm for finding out if an induced subgraph is complete

Question

I have an undirected unweighted graph G = (V, E) and a randomly chosen subset S of its vertices. I want to check whether the vertices in S are mutually adjacent (i.e. form a complete subgraph/a clique).

I have the following algorithm (pseudo-code):

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;

The problem is that this algorithm's worst-case performance is O(|V|²) (in case when the subset S contains all the vertices of a complete graph).

My question is: is there a faster algorithm that runs with a better big O worst-case complexity?

Answer 1

Assuming that you can check whether two vertices are incident in O(1), your algorithm has O(|V|²) = O(|E|) time complexity in the worst case. I don't think you can do better than O(|E|), since you should really check all the edges of the subgraph.

Answer 2

I don't believe you'll get a non O(|E|^2) algorithm for performing this check. Logically, each V1-V2 edge must be sought to prove completeness. Separating into two loops, the first checking the edge counts and the second then checking the vertex connections would potentially speed up the algorithm. Perhaps another way of representing the graph (with edges rather than vertices) would help?

Answer 3

How does your hasEdgeTo perform? If you use a tree-based set to store the edges, that function is not just O(1).

By using a bitvector for the edges, you can go with O(|S| * min(|E|, |V|, |S|)).