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).
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
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