Abstract
In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G=(V,E) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O(Δ 4) time delay, where Δ is the maximum degree of vertices. However, it requires an O(n⋅m) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O(Δ⋅H 3) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{v∈V∣δ(v)≥H}|≤H given δ(v) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than Δ.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akkoyunlu, E.A.: The enumeration of maximal cliques of large graphs. SIAM J. Comput. 2(1), 1–6 (1973)
Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575–576 (1973)
Cheng, J., Ke, Y., Fu, A.W.-C., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks by h*-graph. In: SIGMOD, pp. 447–458 (2010)
Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)
Cohen, S., Fadida, I., Kanza, Y., Kimelfeld, B., Sagiv, Y.: Full disjunctions: Polynomial-delay iterators in action. In: VLDB, pp. 739–750 (2006)
Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. In: WADS, pp. 278–289 (2009)
Harley, E., Bonner, A.J., Goodman, N.: Uniform integration of genome mapping data using intersection graphs. Bioinformatics 17(6), 487–494 (2001)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119–123 (1988)
Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the web for emerging cyber-communities. Comput. Netw. 31(11–16), 1481–1493 (1999)
Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: SWAT, pp. 260–272 (2004)
Modani, N., Dey, K.: Large maximal cliques enumeration in sparse graphs. In: CIKM, pp. 1377–1378 (2008)
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(3), 211–218 (2004)
Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1), 28–42 (2006)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)
Acknowledgement
The work was supported by grants of the Research Grants Council of the Hong Kong SAR, China No. 419008 and 419109.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chang, L., Yu, J.X. & Qin, L. Fast Maximal Cliques Enumeration in Sparse Graphs. Algorithmica 66, 173–186 (2013). https://doi.org/10.1007/s00453-012-9632-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-012-9632-8