# Finding All Cliques of an Undirected Graph

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

• In the worst case you can't beat $2^n$, since that's how many cliques the complete graph $K_n$ has. – Austin Buchanan Jun 23 '16 at 21:41
• If you wish to do this (or other "clique-like computation") in practice, try Cliquer. – Juho Jul 13 '16 at 17:45

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\}$.