Given a graph $G$ with $n >> k$ vertices, what are the fastest algorithms known to count the number of induced subgraphs in $G$ that are $k$-cliques?Are there algorithms that can do better than the inevitable $O(n^k)$ brute force? If there is no general algorithm that is better than $O(n^k)$ known, are there algorithms that run faster when promised the graph is of a specific type/has certain structure?Suppose you only care about the approximate number of such subgraphs, are there faster approximation algorithms?What if $k = 3$ and you want to count the number of triangles in your graph. Are there algorithms that can do faster than $O(n^3)$? What if extra conditions are imposed on $G$?What if the graph is sparse?
Efficient algorithms for counting $k$-clique subgraphs
ds.algorithms;graph algorithms;approximation algorithms;counting complexity