<p>The algorithm of Bron–Kerbosch computes all maximal cliques in an undirected graph (see <a href="http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm" rel="nofollow">Wikipeadia</a>). The worst-case running time is O(3<sup><i>n</i>/3</sup>), apparently it is very fast in general and still is the fastest known algorithm to compute all maximal cliques. For a newer reference see the papers of <a href="http://www.ingentaconnect.com/content/klu/coap/2004/00000027/00000002/05151803" rel="nofollow">V. Stix</a> and <a href="http://hal.inria.fr/docs/00/12/81/30/PDF/RR-5615.pdf" rel="nofollow">Cazals and Karande</a>.</p>

CC BY-SA 3.0
2011-12-03T16:01:00.760Z
To get the $O(3^{n/3})$ bound, we need a little trick for effectively performing branch-and-bound in the backtracking procedure (due to Tomita, Tanaka, and Takahashi).  It's also good to note that the bound of $3^{n/3}$ is worst-case optimal, since there is a graph with $3^{n/3}$ maximal cliques (namely, $K_{3,3,...,3}$).
Yoshio Okamoto
CC BY-SA 3.0
2011-12-03T17:00:54.327Z
For more recent work on Bron–Kerbosch see my papers http://arxiv.org/abs/1006.5440 with Strash and Löffler at ISAAC 2010 and http://arxiv.org/abs/1103.0318 with Strash at SEA 2011. However this doesn't really answer the original poster's question as the algorithm is not output-sensitive: it could take exponential time even when there are only polynomially many maximal cliques.
David Eppstein
CC BY-SA 3.0
2011-12-03T15:13:42.457Z
2011-12-03T15:13:42.457Z
Volker Turau
<p>There are several output-sensitive algorithms to enumerate all maximal cliques in polynomial time per output.  One of the earliest algorithms was developed by Tsukiyama, Ide, Ariyoshi, and Shirakawa (1977).</p>

<ul>
<li>Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: A New Algorithm for Generating All the Maximal Independent Sets. SIAM J. Comput. 6(3): 505-517 (1977)</li>
</ul>

<p>This means that if you know your graph has at most polynomially many maximal cliques, then the total running time of their algorithm will be polynomial in the input size.</p>

CC BY-SA 3.0
2011-12-06T06:03:01.450Z
Unfortunetely, I don't have access to the paper. But I am sure that this is what I am looking for, thank you.
Arman
CC BY-SA 3.0
2011-12-03T15:52:44.180Z
2011-12-03T15:52:44.180Z
Yoshio Okamoto
<p>I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. It concludes that if an oracle reports that a graph $G$ is an EPT graph, then  it is possible to find the maximum clique with a standard clique enumeration algorithm.</p>

<p>First of all, what are these standard clique enumeration algorithms? If there are more than one, can we say that if the number of maximal cliques of a graph is polynomial then can we use <em>any</em> of these enumeration algorithms? Or should we derive a special algorithm from a generic algorithm which uses some special structures of the graph class?</p>

<p>Thanks in advance.</p>

<ds.algorithms><graph-algorithms><clique>
Clique Enumeration Algorithm
Arman
# Clique Enumeration Algorithm

(Asked by: username_0 on 2011-12-03)

I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. It concludes that if an oracle reports that a graph $G$ is an EPT graph, then it is possible to find the maximum clique with a standard clique enumeration algorithm.

First of all, what are these standard clique enumeration algorithms? If there are more than one, can we say that if the number of maximal cliques of a graph is polynomial then can we use *any* of these enumeration algorithms? Or should we derive a special algorithm from a generic algorithm which uses some special structures of the graph class?

Thanks in advance.

**Tags:** ds.algorithms, graph-algorithms, clique


---

## 2 answers

### Answer by username_2 on 2011-12-03. Score: 13 | Accepted answer

There are several output-sensitive algorithms to enumerate all maximal cliques in polynomial time per output. One of the earliest algorithms was developed by Tsukiyama, Ide, Ariyoshi, and Shirakawa (1977).

* Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: A New Algorithm for Generating All the Maximal Independent Sets. SIAM J. Comput. 6(3): 505-517 (1977)

This means that if you know your graph has at most polynomially many maximal cliques, then the total running time of their algorithm will be polynomial in the input size.

> **Comments:**
> **username_0**: Unfortunetely, I don't have access to the paper. But I am sure that this is what I am looking for, thank you.  

---

### Answer by username_1 on 2011-12-03. Score: 4

The algorithm of Bron–Kerbosch computes all maximal cliques in an undirected graph (see [Wikipeadia](http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm)). The worst-case running time is O(3*n*/3), apparently it is very fast in general and still is the fastest known algorithm to compute all maximal cliques. For a newer reference see the papers of [V. Stix](http://www.ingentaconnect.com/content/klu/coap/2004/00000027/00000002/05151803) and [Cazals and Karande](http://hal.inria.fr/docs/00/12/81/30/PDF/RR-5615.pdf).

> **Comments:**
> **username_2**: To get the $O(3^{n/3})$ bound, we need a little trick for effectively performing branch-and-bound in the backtracking procedure (due to Tomita, Tanaka, and Takahashi).  It's also good to note that the bound of $3^{n/3}$ is worst-case optimal, since there is a graph with $3^{n/3}$ maximal cliques (namely, $K_{3,3,...,3}$).  
> **username_3**: For more recent work on Bron–Kerbosch see my papers http://arxiv.org/abs/1006.5440 with Strash and Löffler at ISAAC 2010 and http://arxiv.org/abs/1103.0318 with Strash at SEA 2011. However this doesn't really answer the original poster's question as the algorithm is not output-sensitive: it could take exponential time even when there are only polynomially many maximal cliques.  

---

