-2
$\begingroup$

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

$\endgroup$
  • 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 Buchanan Jun 23 '16 at 21:41
  • $\begingroup$ If you wish to do this (or other "clique-like computation") in practice, try Cliquer. $\endgroup$ – Juho Jul 13 '16 at 17:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.