<p>Eppstein and Strash (2011) show that for a graph <span class="math-container">$G$</span> with degeneracy <span class="math-container">$d$</span> all maximal cliques can be listed in time <span class="math-container">$O(dn3^{d/3})$</span>, where the degeneracy is the smallest number such that every subgraph of <span class="math-container">$G$</span> contains at least one vertex of degree <span class="math-container">$d$</span>. The degeneracy is usually small, and in their paper they provide experimental results on graphs of comparable size, so you may be able to solve your problem using their algorithm.</p>
<p>D. Eppstein, D. Strash, <a href="http://arxiv.org/abs/1103.0318" rel="nofollow noreferrer"><em>Listing All Maximal Cliques in Large Sparse Real-World Graphs</em></a>, 10th International Conference on Experimental Algorithms, 2011.</p>

CC BY-SA 3.0
2011-05-02T05:50:41.657Z
Note that it is easy and fast to obtain all 17-cliques from maximal cliques -- if they are not too big! On $K_n$, you are back to the old problem. But then, why list all 17-cliques if you have a much more concise representation for them?
Raphael
CC BY-SA 3.0
2011-05-02T15:07:29.250Z
Thanks, but our algorithm is intended primarily for graphs in which the numbers of edges and vertices are relatively close to each other. It doesn't sound like that is the case here.
David Eppstein
CC BY-SA 3.0
2011-05-03T10:50:43.740Z
@David: I see; having minimum degree 2000, the above graph will have $d\geq 2000$.
Marcus Ritt
CC BY-SA 3.0
2011-05-02T01:31:56.203Z
2011-05-02T01:31:56.203Z
2020-06-17T09:38:08.363Z
Marcus Ritt
<p>Give Cliquer a try. </p>

<p><a href="http://users.tkk.fi/pat/cliquer.html">http://users.tkk.fi/pat/cliquer.html</a></p>

<p>It's true your graph is huge, but sometimes it works. And it doesn't take long to try it as this software is already (and well) coded :-)</p>

<p>Nathann</p>

CC BY-SA 3.0
2011-05-06T21:28:41.777Z
Yes. Cliquer to the rescue. Take your graph and split it into 8,568 graphs; one for each node and it's neighbors. Also, as you make a graph for each node and it's induced neighborhood remove it from the super graph; thus the problem graphs will get smaller and smaller as you go.

Also, do some pre-cleaning by iteratively removing all nodes in these smaller graphs that do not have 16 neighbors.
Chad Brewbaker
CC BY-SA 3.0
2011-05-02T05:39:39.823Z
2011-05-02T05:39:39.823Z
Nathann Cohen
<p>The <a href="https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf" rel="nofollow noreferrer">1985 paper by Nešetřil and Poljak</a> linked in <a href="https://math.stackexchange.com/a/1279764/50512">this answer</a> to a similar question suggests that you can search for the subgraph <span class="math-container">$K_{3\ell+i}$</span> in time <span class="math-container">$O(n^{i+\ell ω})$</span>, where <span class="math-container">$ω$</span> is the matrix multiplication constant.
Wikipedia says only Strassen’s algorithm with <span class="math-container">$ω \approx 2.807$</span> is usable in practice. This would give you roughly <span class="math-container">$O(n^{14.037})$</span> for finding your <span class="math-container">$K_{17}$</span>, I believe.</p>
<p>Probably still not useful to solve your actual problem, but at least “better” than the naive <span class="math-container">$O(n^{17})$</span>…</p>

CC BY-SA 4.0
2022-11-02T13:41:39.697Z
2022-11-02T13:41:39.697Z
Max Merz
<p>I'm not seeing why the CLRS (p. 617) version of Strongly-Connected-Components() doesn't solve your problem. And it's just 2 DFS's to find all cliques of any size. So, when you're done, you just restrict the result set to those cliques with 17 vertices. That's just O(n + k) because DFS is the limiting factor.
The structure of your graph might also make your idea of deleting vertices of degree 16 a nice way to speed things up.
2 DFS's on 12.8M edges certainly is likely not going to be blazingly fast, but I would think it would be doable in a reasonable amount of time. I'm unfortunately not seeing how you could multi-thread it.
I've got some Java code that does a DFS and stronglyConnectedComponents() if you think it might be of use to you (my email: info@marshallfarrier.com; and please do email me if you're interested, as I'd be interested to see how my code works on something that big!).
Or am I misunderstanding the problem altogether? (if so, my apologies)</p>

CC BY-SA 3.0
2011-05-02T08:16:21.263Z
A clique is not the same thing as a strongly connected component.
Dave Clarke
CC BY-SA 3.0
2011-05-02T13:17:09.583Z
tx, now i see what the difference is.
marshallf
CC BY-SA 3.0
2011-05-02T04:17:20.103Z
2011-05-02T04:17:20.103Z
marshallf
<p>These kind of problems are in general very hard with the decission version of a problem often being NP-hard, so I doubt you will find an algorithm fast enough, unless your graph has some peculiarity which allows you to discard a large number of vertices.</p>

<p>Since you restrict it to cliques of exactly 17 vertices then trivially there is an $O(n^{17})$ algorithm, but I'd hardly call this fast. To do this simply step through all subsets of 17 vertices in lexicographical order and check whether they form a clique. Note that this is exactly $\binom{n}{17}$ subsets. Note however, that for an input graph which is itself a clique, there are $\binom{n}{17}$ cliques of comprised of 17 vertices, and hence this trivial algorithm is optimal if we consider only worst case scaling, since simply reading a list of all such cliques takes $\binom{n}{17}$ steps. In order to do better than this, you need a graph with some structure.</p>

<p>So for your specific case of $n=8568$ you potentially have $2 \times 10^{52}$ cliques of 17 vertices. Further since you have more than 12 million edges, this is enough for a maximally connected graph of 5000 vertices, which would have approximately $2 \times 10^{48}$ unique subsets 17 vertices which form cliques, so for the parameters you have listed it is entirely possible that you simply cannot enumerate cliques fast enough to give you a reasonable run time.</p>

CC BY-SA 3.0
2011-05-02T04:25:12.330Z
Note that only about 34.6% of all possible edges exist in the graph.  So, if the graph is similar to a graph generated by choosing uniformly among all edges (note, this is a big assumption) then each set of 17 nodes has probability of about $2.6 \times 10^{-63}$ of being a clique.  As such, it's likely that the problem will not be listing the cliques, but rather verifying that one does not exist.
bbejot
CC BY-SA 3.0
2011-05-02T14:34:54.480Z
Yes, but it is impossible to tell without more info.
Joe Fitzsimons
CC BY-SA 3.0
2011-05-01T21:20:45.267Z
2011-05-01T22:26:07.897Z
2011-05-01T22:26:07.897Z
Joe Fitzsimons
<p>I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques should have exactly 17 vertices.</p>

<p>The algorithm should be fast, because of the size of the graph.</p>

<p>I had the following idea:</p>

<ul>
<li>Delete all vertices with a degree of 16 or less.</li>
<li>Iterate over every vertex
<ul>
<li>try to add another vertex:
<ul>
<li>If the clique has exactly 17 vertices: Add it to a list</li>
<li>Else: Keep trying to add vertices</li>
</ul></li>
<li>If no more vertices can be added: go back to the latest point where you had the choice to add some vertices and add one of those that could not be added before.</li>
</ul></li>
</ul>

<p>I didn't implement this algorithm, because I think it will be quite slow. Do you know better ones?</p>

CC BY-SA 3.0
2011-05-01T21:07:29.343Z
I would guess that there is no known algorithm which works in reasonable amount of time with every graph with that many vertices and edges.  Therefore, if there is an algorithm which works fast enough with your graph, it must depend on the details of your graph.  This means that whether a particular algorithm is “better” or not depends on the information you did not provide in the question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-07T02:38:30.947Z
Depending on the structure of the graph, the algorithm in the paper of Jennifer Debroni, Wendy Myrvold, myself *et al* recently in SODA might have a shot at finding them. What it needs to work well is related to *why* the maximal cliques in your graph have at most 17 vertices.
Peter Shor 
<ds.algorithms><graph-algorithms><exp-time-algorithms><clique>
Finding cliques in a big graph
Martin Thoma
# Finding cliques in a big graph

(Asked by: username_0 on 2011-05-01)

I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques should have exactly 17 vertices.

The algorithm should be fast, because of the size of the graph.

I had the following idea:

* Delete all vertices with a degree of 16 or less.
* Iterate over every vertex
  + try to add another vertex:
    - If the clique has exactly 17 vertices: Add it to a list
    - Else: Keep trying to add vertices
  + If no more vertices can be added: go back to the latest point where you had the choice to add some vertices and add one of those that could not be added before.

I didn't implement this algorithm, because I think it will be quite slow. Do you know better ones?

**Tags:** ds.algorithms, graph-algorithms, exp-time-algorithms, clique
> **Comments:**
> **username_1**: I would guess that there is no known algorithm which works in reasonable amount of time with every graph with that many vertices and edges.  Therefore, if there is an algorithm which works fast enough with your graph, it must depend on the details of your graph.  This means that whether a particular algorithm is “better” or not depends on the information you did not provide in the question.  
> **username_2**: Depending on the structure of the graph, the algorithm in the paper of Jennifer Debroni, Wendy Myrvold, myself *et al* recently in SODA might have a shot at finding them. What it needs to work well is related to *why* the maximal cliques in your graph have at most 17 vertices.  

---

## 5 answers

### Answer by username_11 on 2011-05-01. Score: 10 | Accepted answer

These kind of problems are in general very hard with the decission version of a problem often being NP-hard, so I doubt you will find an algorithm fast enough, unless your graph has some peculiarity which allows you to discard a large number of vertices.

Since you restrict it to cliques of exactly 17 vertices then trivially there is an $O(n^{17})$ algorithm, but I'd hardly call this fast. To do this simply step through all subsets of 17 vertices in lexicographical order and check whether they form a clique. Note that this is exactly $\binom{n}{17}$ subsets. Note however, that for an input graph which is itself a clique, there are $\binom{n}{17}$ cliques of comprised of 17 vertices, and hence this trivial algorithm is optimal if we consider only worst case scaling, since simply reading a list of all such cliques takes $\binom{n}{17}$ steps. In order to do better than this, you need a graph with some structure.

So for your specific case of $n=8568$ you potentially have $2 \times 10^{52}$ cliques of 17 vertices. Further since you have more than 12 million edges, this is enough for a maximally connected graph of 5000 vertices, which would have approximately $2 \times 10^{48}$ unique subsets 17 vertices which form cliques, so for the parameters you have listed it is entirely possible that you simply cannot enumerate cliques fast enough to give you a reasonable run time.

> **Comments:**
> **username_12**: Note that only about 34.6% of all possible edges exist in the graph.  So, if the graph is similar to a graph generated by choosing uniformly among all edges (note, this is a big assumption) then each set of 17 nodes has probability of about $2.6 \times 10^{-63}$ of being a clique.  As such, it's likely that the problem will not be listing the cliques, but rather verifying that one does not exist.  
> **username_11**: Yes, but it is impossible to tell without more info.  

---

### Answer by username_3 on 2011-05-02. Score: 10

Eppstein and Strash (2011) show that for a graph $G$ with degeneracy $d$ all maximal cliques can be listed in time $O(dn3^{d/3})$, where the degeneracy is the smallest number such that every subgraph of $G$ contains at least one vertex of degree $d$. The degeneracy is usually small, and in their paper they provide experimental results on graphs of comparable size, so you may be able to solve your problem using their algorithm.

D. Eppstein, D. Strash, [*Listing All Maximal Cliques in Large Sparse Real-World Graphs*](http://arxiv.org/abs/1103.0318), 10th International Conference on Experimental Algorithms, 2011.

> **Comments:**
> **username_4**: Note that it is easy and fast to obtain all 17-cliques from maximal cliques -- if they are not too big! On $K_n$, you are back to the old problem. But then, why list all 17-cliques if you have a much more concise representation for them?  
> **username_5**: Thanks, but our algorithm is intended primarily for graphs in which the numbers of edges and vertices are relatively close to each other. It doesn't sound like that is the case here.  
> **username_3**: @David: I see; having minimum degree 2000, the above graph will have $d\geq 2000$.  

---

### Answer by username_6 on 2011-05-02. Score: 8

Give Cliquer a try.

<http://users.tkk.fi/pat/cliquer.html>

It's true your graph is huge, but sometimes it works. And it doesn't take long to try it as this software is already (and well) coded :-)

Nathann

> **Comments:**
> **username_7**: Yes. Cliquer to the rescue. Take your graph and split it into 8,568 graphs; one for each node and it's neighbors. Also, as you make a graph for each node and it's induced neighborhood remove it from the super graph; thus the problem graphs will get smaller and smaller as you go.  Also, do some pre-cleaning by iteratively removing all nodes in these smaller graphs that do not have 16 neighbors.  

---

### Answer by username_8 on 2022-11-02. Score: 1

The [1985 paper by Nešetřil and Poljak](https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf) linked in [this answer](https://math.stackexchange.com/a/1279764/50512) to a similar question suggests that you can search for the subgraph $K\_{3\ell+i}$ in time $O(n^{i+\ell ω})$, where $ω$ is the matrix multiplication constant.
Wikipedia says only Strassen’s algorithm with $ω \approx 2.807$ is usable in practice. This would give you roughly $O(n^{14.037})$ for finding your $K\_{17}$, I believe.

Probably still not useful to solve your actual problem, but at least “better” than the naive $O(n^{17})$…


---

### Answer by username_9 on 2011-05-02. Score: -3

I'm not seeing why the CLRS (p. 617) version of Strongly-Connected-Components() doesn't solve your problem. And it's just 2 DFS's to find all cliques of any size. So, when you're done, you just restrict the result set to those cliques with 17 vertices. That's just O(n + k) because DFS is the limiting factor.
The structure of your graph might also make your idea of deleting vertices of degree 16 a nice way to speed things up.
2 DFS's on 12.8M edges certainly is likely not going to be blazingly fast, but I would think it would be doable in a reasonable amount of time. I'm unfortunately not seeing how you could multi-thread it.
I've got some Java code that does a DFS and stronglyConnectedComponents() if you think it might be of use to you (my email: info@marshallfarrier.com; and please do email me if you're interested, as I'd be interested to see how my code works on something that big!).
Or am I misunderstanding the problem altogether? (if so, my apologies)

> **Comments:**
> **username_10**: A clique is not the same thing as a strongly connected component.  
> **username_9**: tx, now i see what the difference is.  

---

