# Fastest known algorithm to enumerate k-cliques in a graph for fixed k

Is the best known algorithm for finding all $$k$$-cliques in a graph with $$n$$ nodes, for a fixed $$k$$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ? The time-complexity of the proposed algorithm is $$O(n^k / (\epsilon \log n)^{k-1})$$ with $$O(n^\epsilon)$$ space, for all $$\epsilon > 0$$. Please let me know if there are more efficient algorithms to enumerate all $$k$$-cliques in a graph.

• Probably useless comment - have you looked through the papers that cite that article? Available here: scholar.google.com/… May 23, 2020 at 4:45
• What are your assumptions about the density of the graph? Because it's easy to enumerate $k$-cliques in time $O(m^{k/2})$ and this can be significantly faster for sparse graphs. May 23, 2020 at 18:28
• @DavidEppstein I don't make any assumptions about the density of the graph but its interesting to see that better results can be achieved on doing so. I came across some interesting work -> dl.acm.org/doi/abs/10.1145/3188745.3188810 where they can get the count of $k$-cliques in sublinear time, but they don't enumerate the cliques.
– cbro
May 24, 2020 at 6:47
• If you insist on enumerating $k$-cliques, without any assumption on the graph, it seems that you cannot do significantly better than $O({n\choose k})$ because any set of $k$ vertices in a complete graph is a $k$-clique. (I assume you don't allow cheating on the output part.) May 28, 2020 at 6:26
• About listing k-cliques for fixed k in sparse graphs: papers-gamma.link/paper/32 Jan 3, 2021 at 0:01