1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – foobarbaz Apr 29 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.