Question

1) Consider the clique problem: given a graph G (V, E) and a positive integer k, determine whether the graph contains a clique of size k, i.e., a set of k vertices S of V such that each pair of vertices of S are neighbours to each other. Design an exhaustive-search algorithm for this problem. Compute also the time complexity of your algorithm.

Answer 1

Algorithm: Max-Clique (G, k, v) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success 

let count be an integer
set count to 0
for each vertex v in V’
    remove all edges adjacent to v from set E
    increment count by 1
    if count = k and E is empty
    then
        the given solution is correct
    else
        the given solution is wrong