3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Probably useless comment - have you looked through the papers that cite that article? Available here: scholar.google.com/… $\endgroup$ – Lorenzo Najt May 23 at 4:45
  • 1
    $\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$ – David Eppstein May 23 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 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 at 6:26

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.