CODEWITHSUNDEEP
algorithmoptimizationgraph
Karel Petranek
Karel Petranek

Reputation: 15154

Fast algorithm for finding out if an induced subgraph is complete

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|2) (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?

Upvotes: 6

Views: 829

Answers (3)

Albert
Albert

Reputation: 68110

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|)).

Upvotes: 2

Will A
Will A

Reputation: 24988

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?

Upvotes: 2

Bolo
Bolo

Reputation: 11690

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.

Upvotes: 4

Related Questions