How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)
2
-
2$\begingroup$ In the worst case you can't beat $2^n$, since that's how many cliques the complete graph $K_n$ has. $\endgroup$– Austin BuchananJun 23, 2016 at 21:41
-
$\begingroup$ If you wish to do this (or other "clique-like computation") in practice, try Cliquer. $\endgroup$– JuhoJul 13, 2016 at 17:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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:
- Vertex set is the set of elements in $\mathcal{I}$
- 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.
