9
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Unfortunetely, I don't have access to the paper. But I am sure that this is what I am looking for, thank you. $\endgroup$ – Arman Dec 6 '11 at 6:03
4
$\begingroup$

The algorithm of Bron–Kerbosch computes all maximal cliques in an undirected graph (see Wikipeadia). The worst-case running time is O(3n/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 and Cazals and Karande.

$\endgroup$
  • 2
    $\begingroup$ 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}$). $\endgroup$ – Yoshio Okamoto Dec 3 '11 at 16:01
  • 1
    $\begingroup$ For more recent work on Bron–Kerbosch see my papers arxiv.org/abs/1006.5440 with Strash and Löffler at ISAAC 2010 and 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. $\endgroup$ – David Eppstein Dec 3 '11 at 17:00

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.