I am having trouble getting my head around what the complexity of the verification step for the CLIQUE problem would be -- specifically if an adjacency matrix is used. I know in general the complexity for this problem would be O(k^2) * edges in G.
This is the specific question I am attempting to solve: Select the correct complexity of the verification step for CLIQUE problem. Assume that the candidate solution is size k, and that the Graph with n vertices is represented by an adjacency matrix (i.e., constant time edge lookups).
My thoughts:
If there are k vertices in the candidate solution, I will need to iterate k
times. For each of those vertices I will need to check that corresponding row in the adjacency matrix to see if the sum of that row is k - 1.
in other words checking to see if the deg(k)
for each k
is k-1
.
Should I consider that k^2
? Or would it be (k^2 * n)
since I would need to add 1 for each of the n vertices on that row to find out if the row sum is k-1
?