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

CC BY-SA 4.0
2020-05-23T04:45:16.093Z
Probably useless comment - have you looked through the papers that cite that article? Available here: https://scholar.google.com/scholar?cites=11230550825184440674&as_sdt=5,50&sciodt=0,50&hl=en
Elle Najt
CC BY-SA 4.0
2020-05-23T18:28:51.080Z
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.
David Eppstein
CC BY-SA 4.0
2020-05-24T06:47:05.733Z
@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 -> https://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.
user43464
CC BY-SA 4.0
2020-05-28T06:26:18.920Z
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.)
Yixin Cao
CC BY-SA 4.0
2021-01-03T00:01:05.300Z
About listing k-cliques for fixed k in sparse graphs: https://papers-gamma.link/paper/32
maxdan94
<time-complexity><clique><space-complexity>
Fastest known algorithm to enumerate k-cliques in a graph for fixed k
user43464
# Fastest known algorithm to enumerate k-cliques in a graph for fixed k

(Asked by: username_0 on 2020-05-22)

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.

**Tags:** time-complexity, clique, space-complexity
> **Comments:**
> **username_1**: Probably useless comment - have you looked through the papers that cite that article? Available here: https://scholar.google.com/scholar?cites=11230550825184440674&as_sdt=5,50&sciodt=0,50&hl=en  
> **username_2**: 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.  
> **username_0**: @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 -> https://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.  
> **username_3**: 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.)  
> **username_4**: About listing k-cliques for fixed k in sparse graphs: https://papers-gamma.link/paper/32  

---

## 0 answers

