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:
- How many subgraphs of size k can we generate, in Θ notation as a function of n, m and k? (and why is it so)
- 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.