×

The worst-case time complexity for generating all maximal cliques and computational experiments. (English) Zbl 1153.68398

Summary: We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron-Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is \(O(3^{n/3})\) for an \(n\)-vertex graph. This is optimal as a function of \(n\), since there exist up to \(3^{n/3}\) maximal cliques in an \(n\)-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] T. Akutsu, M. Hayashida, D.K.C. Bahadur, E. Tomita, J. Suzuki, K. Horimoto, Dynamic programming and clique based approaches for protein threading with profiles and constraints, IEICE Trans. Fund. Electron. Commun. Comput. Sci. E89-A (2006) 1215-1222.; T. Akutsu, M. Hayashida, D.K.C. Bahadur, E. Tomita, J. Suzuki, K. Horimoto, Dynamic programming and clique based approaches for protein threading with profiles and constraints, IEICE Trans. Fund. Electron. Commun. Comput. Sci. E89-A (2006) 1215-1222.
[2] Bahadur, D. K.C.; Akutsu, T.; Tomita, E.; Seki, T.; Fujiyama, A., Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms, Genome Inform., 13, 143-152 (2002)
[3] Bahadur, D. K.C.; Tomita, E.; Suzuki, J.; Akutsu, T., Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach, J. Bioinform. Comput. Biol., 3, 103-126 (2005)
[4] Bahadur, D. K.C.; Tomita, E.; Suzuki, J.; Horimoto, K.; Akutsu, T., Protein threading with profiles and distance constraints using clique based algorithms, J. Bioinform. Comput. Biol., 4, 19-42 (2006)
[5] I.M. Bomze, M. Budinich, P.M. Pardalos, M. Pelillo, The maximum clique problem, in: D.-Z. Du, P.M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Supplement Vol. A, Kluwer Academic Publishers, Dordrecht, 1999, pp. 1-74.; I.M. Bomze, M. Budinich, P.M. Pardalos, M. Pelillo, The maximum clique problem, in: D.-Z. Du, P.M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Supplement Vol. A, Kluwer Academic Publishers, Dordrecht, 1999, pp. 1-74. · Zbl 1253.90188
[6] Bron, C.; Kerbosch, J., Algorithm 457, finding all cliques of an undirected graph, Comm. ACM, 16, 575-577 (1973) · Zbl 0261.68018
[7] Chiba, N.; Nishizeki, T., Arboricity and subgraph listing algorithms, SIAM J. Comput., 14, 210-223 (1985) · Zbl 0572.68053
[8] Hattori, M.; Okuno, Y.; Goto, S.; Kanehisa, M., Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways, J. Amer. Chem. Soc., 125, 11853-11865 (2003)
[9] Johnston, H. C., Cliques of a graph—variations on the Bron-Kerbosch algorithm, Int. J. Comput. Inform. Sci., 5, 209-238 (1976) · Zbl 0401.68042
[10] D.S. Johnson, M.A. Trick (Eds.), Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26, American Mathematical Society, Providence, RI, 1996.; D.S. Johnson, M.A. Trick (Eds.), Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26, American Mathematical Society, Providence, RI, 1996.
[11] Kobayashi, S.; Kondo, T.; Okuda, K.; Tomita, E., Extracting globally structure free sequences by local structure freeness, Proc. DNA, 9, 206 (2003)
[12] Koch, I., Enumerating all connected maximal common subgraphs in two graphs, Theoret. Comput. Sci., 250, 1-30 (2001) · Zbl 0952.68105
[13] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9, 558-565 (1980) · Zbl 0445.68054
[14] K. Makino, T. Uno, New algorithms for enumerating all maximal cliques, SWAT 2004, Lecture Notes in Computer Science, Vol. 3111, 2004, pp. 260-272.; K. Makino, T. Uno, New algorithms for enumerating all maximal cliques, SWAT 2004, Lecture Notes in Computer Science, Vol. 3111, 2004, pp. 260-272. · Zbl 1095.68626
[15] Mohseni-Zadeh, S.; Brézellec, P.; Risler, J.-L., Cluster-C, an algorithm for the large-scale clustering of protein sequences based on the extraction of maximal cliques, Comput. Biol. Chem., 28, 211-218 (2004) · Zbl 1088.92024
[16] Mohseni-Zadeh, S.; Louis, A.; Brézellec, P.; Risler, J.-L., PHYTOPROT: a database of clusters of plant proteins, Nucleic Acids Res., 32, D351-D353 (2004)
[17] Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 3, 23-28 (1965) · Zbl 0144.23205
[18] T. Nakagawa, E. Tomita, Experimental comparisons of algorithms for generating all maximal cliques, Technical Report of IPSJ, 2004-MPS-52, 2004, pp. 41-44.; T. Nakagawa, E. Tomita, Experimental comparisons of algorithms for generating all maximal cliques, Technical Report of IPSJ, 2004-MPS-52, 2004, pp. 41-44.
[19] Pardalos, P. M.; Xue, J., The maximum clique problem, J. Global Optim., 4, 301-328 (1994) · Zbl 0797.90108
[20] Robson, J. M., Algorithms for maximum independent sets, J. Algorithms, 7, 425-440 (1986) · Zbl 0637.68080
[21] Tarjan, R. E.; Trojanowski, A. E., Finding a maximum independent set, SIAM J. Comput., 6, 537-546 (1977) · Zbl 0357.68035
[22] Y. Sutani, E. Tomita, Computational experiments and analyses of a more efficient algorithm for finding a maximum clique, Technical Report of IPSJ, 2005-MPS-57, 2005, pp. 45-48, and others.; Y. Sutani, E. Tomita, Computational experiments and analyses of a more efficient algorithm for finding a maximum clique, Technical Report of IPSJ, 2005-MPS-57, 2005, pp. 45-48, and others. · Zbl 1038.68565
[23] E. Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for finding all the cliques, Technical Report of the University of Electro-Communications, UEC-TR-C5(2), 1988.; E. Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for finding all the cliques, Technical Report of the University of Electro-Communications, UEC-TR-C5(2), 1988. · Zbl 1091.68562
[24] E. Tomita, A. Tanaka, H. Takahashi, An optimal algorithm for finding all the cliques, Technical Report of IPSJ, 1989-AL-12, 1989, pp. 91-98.; E. Tomita, A. Tanaka, H. Takahashi, An optimal algorithm for finding all the cliques, Technical Report of IPSJ, 1989-AL-12, 1989, pp. 91-98.
[25] E. Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for generating all maximal cliques, COCOON 2004, Lecture Notes in Computer Science, Vol. 3106, 2004, pp. 161-170.; E. Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for generating all maximal cliques, COCOON 2004, Lecture Notes in Computer Science, Vol. 3106, 2004, pp. 161-170. · Zbl 1091.68562
[26] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6, 505-517 (1977) · Zbl 0364.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.