2
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\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?

Improve this answer
$\endgroup$
1
  • $\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, 2018 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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