Question

Clique: A graph clique of size k is a subset of k nodes that are all connected to each other (complete subgraph of size k). Design an exhaustive-search algorithm in PSEUDOCODE that takes as input a graph G, an integer k and check if a clique of size k exists in G. ANALYZE the runtime of your algorithm.

Answer 1

Pseudocode Algorithm:

Max-Clique (G, k, v)
S := 0
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

For count:

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 answer is correct
else
the given answer is wrong