<p>If C is a maximal clique, any subset is a clique, ie the set of cliques in a graph forms an independent system. If the independent system $\mathcal{I}$ on ground set $V$ is given by an oracle $O$ which runs in time $p_{\mathcal{I}}$, then the elements of  $\mathcal{I}$ can be listed with delay $|V|\cdot p_{\mathcal{I}}$ (with a backtrack algorithm). Take any linear ordering of V and consider the following graph:</p>

<ol>
<li>Vertex set is the set of elements in $\mathcal{I}$</li>
<li>If $C\in \mathcal{I}$, then for each $a&gt;max(C)$ such that $C\cup \{a\} \in \mathcal{I}$, put an edge $C-C\cup\{a\}$. </li>
</ol>

<p>A traversal of this graph can be done by a standard Depth First Search.</p>

CC BY-SA 3.0
2016-06-24T08:34:44.433Z
2016-06-24T08:34:44.433Z
M. kanté
<p>How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)</p>

CC BY-SA 3.0
2016-06-23T21:41:22.363Z
In the worst case you can't beat $2^n$, since that's how many cliques the complete graph $K_n$ has.
Austin Buchanan
CC BY-SA 3.0
2016-07-13T17:45:28.750Z
If you wish to do this (or other "clique-like computation") in practice, try [Cliquer](https://users.aalto.fi/~pat/cliquer.html).
Juho
<graph-theory><graph-algorithms><clique>
Finding All Cliques of an Undirected Graph
Chadi
# Finding All Cliques of an Undirected Graph

(Asked by: username_0 on 2016-06-23)

How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)

**Tags:** graph-theory, graph-algorithms, clique
> **Comments:**
> **username_1**: In the worst case you can't beat $2^n$, since that's how many cliques the complete graph $K_n$ has.  
> **username_2**: If you wish to do this (or other "clique-like computation") in practice, try [Cliquer](https://users.aalto.fi/~pat/cliquer.html).  

---

## 1 answers

### Answer by username_3 on 2016-06-24. Score: 1

If C is a maximal clique, any subset is a clique, ie the set of cliques in a graph forms an independent system. If the independent system $\mathcal{I}$ on ground set $V$ is given by an oracle $O$ which runs in time $p\_{\mathcal{I}}$, then the elements of $\mathcal{I}$ can be listed with delay $|V|\cdot p\_{\mathcal{I}}$ (with a backtrack algorithm). Take any linear ordering of V and consider the following graph:

1. Vertex set is the set of elements in $\mathcal{I}$
2. If $C\in \mathcal{I}$, then for each $a>max(C)$ such that $C\cup \{a\} \in \mathcal{I}$, put an edge $C-C\cup\{a\}$.

A traversal of this graph can be done by a standard Depth First Search.


---

