# Complexity of Verification for Clique with Adjacency Matrix

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?

## 1 Answer

Here is an algorithm for verifying that the clique $C[1],\ldots,C[k]$ is contained in the graph whose adjacency matrix is $A$:

for i from 1 to k:
for j from 1 to i-1:
if A[i,j] = "no edge", then return "No"
return "Yes"


What is the running time of this algorithm?

• Outer loop executes k times. On the first inner loop executes once but continues to increment by one so total executions look like 1,2,3,4...k. This is equivalent to k(k+1)/2 = 1/2(k^2 + 1) = O(k^2) Apr 29 '18 at 16:35