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.

  • 2
    $\begingroup$ Probably useless comment - have you looked through the papers that cite that article? Available here: scholar.google.com/… $\endgroup$
    – Elle Najt
    May 23, 2020 at 4:45
  • 2
    $\begingroup$ 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. $\endgroup$ May 23, 2020 at 18:28
  • $\begingroup$ @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. $\endgroup$
    – cbro
    May 24, 2020 at 6:47
  • $\begingroup$ 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.) $\endgroup$
    – Yixin Cao
    May 28, 2020 at 6:26
  • $\begingroup$ About listing k-cliques for fixed k in sparse graphs: papers-gamma.link/paper/32 $\endgroup$
    – maxdan94
    Jan 3, 2021 at 0:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.