Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

Question

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G.

My algorithm is as follows:

Generate all subgraphs of size k, and check each one to determine if it is a valid clique.

I'm trying to find the time complexity of my algorithm, but I'm stuck on how to show it as a function of all three n, m and k.

Where n is the number of vertices in the graph, m is the number of edges and k is the specified size we are looking for.

I need to answer the following:

1. How many subgraphs of size k can we generate, in Θ notation as a function of n, m and k? (and why is it so)
2. What is the worst case time complexity of the algorithm, in O notation as a function of n, m and k? (and why is it so)

so far, I have the following:

• there are O(n^k) subgraphs to check
• worst case run time of the algorithm is O(n^kk^2)
• because there are O(n^k) subgraphs to check, each of which has O(k^2) edges

but I need it bound it in terms of m, the number of edges in the graph as well.

Answer 1

There are $\binom{n}{k}$ sets of $k$ vertices out of $n$, to check that they are actually a clique you need to check $\binom{k}{2}$ pairs to see if they are edges, for a total of $\binom{n}{k} \binom{k}{2}$ edge checks. If you store the graph as an adjacency matrix, each check is $O(1)$. So in all:

$\begin{align*} \binom{n}{k} \binom{k}{2} O(1) &= O(n^k) O(k^2) O(1) \\ &= O(n^k k^2) \end{align*}$

Answer 2

You should check combination $$\binom{n}{k}$$ and each check need $\mathcal{O}(n+m)$ because you should check any subset of vertices with size $k$ form a complete graph or not, so overall running time is $$\binom{n}{k}\mathcal{O}(n+m)=\mathcal{O}\left(n^k(n+m)\right).$$