Skip to main content
SpringerLink
Log in

Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time

  • Conference paper
Algorithms and Computation (ISAAC 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6506))

Included in the following conference series:

Abstract

The degeneracy of an n-vertex graph G is the smallest number d such that every subgraph of G contains a vertex of degree at most d. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron–Kerbosch algorithm and show that it runs in time O(dn3d/3). We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an n-vertex graph with degeneracy d (when d is a multiple of 3 and n ≥ d + 3) is (n − d)3d/3. Therefore, our algorithm matches the Θ(d(n − d)3d/3) worst-case output size of the problem whenever n − d = Ω(n).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Akkoyunlu, E.A.: The enumeration of maximal cliques of large graphs. SIAM J. Comput. 2(1), 1–6 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544–556 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Augustson, J.G., Minker, J.: An analysis of some graph theoretical cluster techniques. J. ACM 17(4), 571–588 (1970)

    Article  MATH  Google Scholar 

  4. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Batagelj, V., Zaveršnik, M.: An O(m) algorithm for cores decomposition of networks (2003)

    Google Scholar 

  6. Berry, N.M., Ko, T.H., Moy, T., Smrcka, J., Turnley, J., Wu, B.: Emergent clique formation in terrorist recruitment. In: Dignum, V., Corkill, D., Jonker, C., Dignum, F. (eds.) Proc. AAAI 2004 Worksh. Agent Organizations. AAAI Press, Menlo Park (2004), http://www.aaai.org/Papers/Workshops/2004/WS-04-02/WS04-02-005.pdf

    Google Scholar 

  7. Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)

    Article  MATH  Google Scholar 

  8. Cai, L., Chan, S., Chan, S.: Random separation: A new method for solving fixed-cardinality optimization problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 239–250. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Cazals, F., Karande, C.: A note on the problem of reporting maximal cliques. Theor. Comput. Sci. 407(1-3), 564–568 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86(2), 243–266 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  12. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comput. Sci. 141(1-2), 109–131 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  13. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)

    Book  MATH  Google Scholar 

  14. Du, N., Wu, B., Pei, X., Wang, B., Xu, L.: Community detection in large-scale social networks. In: Proc. 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis, pp. 16–25 (2007)

    Google Scholar 

  15. Eppstein, D.: Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms & Applications 7(2), 131–140 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  16. Eppstein, D.: All maximal independent sets and dynamic dominance for sparse graphs. ACM Trans. Algorithms 5(4), A38 (2009)

    Google Scholar 

  17. Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. In: WADS 2009. LNCS, vol. 5664, pp. 278–289. Springer, Heidelberg (2009)

    Google Scholar 

  18. Erdős, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Mathematica Hungarica 17(1-2), 61–99 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  19. Frank, O.: Statistical analysis of change in networks. Statistica Neerlandica 45(3), 283–293 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  20. Frank, O., Strauss, D.: Markov graphs. J. Am. Stat. Assoc. 81(395), 832–842 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  21. Freuder, E.C.: A sufficient condition for backtrack-free search. J. ACM 29(1), 24–32 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gardiner, E.J., Willett, P., Artymiuk, P.J.: Graph-theoretic techniques for macromolecular docking. J. Chem. Inf. Comput. Sci. 40(2), 273–279 (2000)

    Article  Google Scholar 

  23. Gerhards, L., Lindenberg, W.: Clique detection for nondirected graphs: Two new algorithms. Computing 21(4), 295–322 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  24. Goel, G., Gustedt, J.: Bounded arboricity to determine the local structure of sparse graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 159–167. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  25. Golovach, P.A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 195–205. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  26. Grindley, H.M., Artymiuk, P.J., Rice, D.W., Willett, P.: Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol. Biol. 229(3), 707–721 (1993)

    Article  Google Scholar 

  27. Harary, F.: Graph Theory. Addison-Wesley, Reading (1972)

    MATH  Google Scholar 

  28. Harary, F., Ross, I.C.: A procedure for clique detection using the group matrix. Sociometry 20(3), 205–215 (1957)

    Article  MathSciNet  Google Scholar 

  29. Horaud, R., Skordas, T.: Stereo correspondence through feature grouping and maximal cliques. IEEE Trans. Patt. An. Mach. Int. 11(11), 1168–1180 (1989)

    Article  Google Scholar 

  30. Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley Interscience, New York (1995)

    MATH  Google Scholar 

  31. Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal in- dependent sets. Inf. Proc. Lett. 27(3), 119–123 (1988)

    Article  MATH  Google Scholar 

  32. Johnston, H.C.: Cliques of a graph—variations on the Bron–Kerbosch algorithm. Int. J. Parallel Programming 5(3), 209–238 (1976)

    MathSciNet  MATH  Google Scholar 

  33. Kirousis, L., Thilikos, D.: The linkage of a graph. SIAM J. Comput. 25(3), 626–647 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  34. Kloks, T., Cai, L.: Parameterized tractability of some (efficient) Y-domination variants for planar graphs and t-degenerate graphs. In: Proc. International Computer Symposium (2000), http://hdl.handle.net/2377/2482

  35. Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. Theor. Comput. Sci. 250(1-2), 1–30 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  36. Koch, I., Lengauer, T., Wanke, E.: An algorithm for finding maximal common subtopologies in a set of protein structures. J. Comput. Biol. 3(2), 289–306 (1996)

    Article  Google Scholar 

  37. 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(3), 558–565 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  38. Lick, D.R., White, A.T.: k-degenerate graphs. Canad. J. Math. 22, 1082–1096 (1970), http://www.smc.math.ca/cjm/v22/p1082

    Article  MathSciNet  MATH  Google Scholar 

  39. Loukakis, E., Tsouros, C.: A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically. Computing 27(4), 349–366 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  40. Luce, R.D., Perry, A.D.: A method of matrix analysis of group structure. Psychometrika 14(2), 95–116 (1949)

    Article  MathSciNet  Google Scholar 

  41. Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 260–272. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  42. Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3(1), 23–28 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  43. Mulligan, G.D., Corneil, D.G.: Corrections to Bierstone’s algorithm for generating cliques. J. ACM 19(2), 244–247 (1972)

    Article  MATH  Google Scholar 

  44. Robins, G., Morris, M.: Advances in exponential random graph (p*) models. Social Networks 29(2), 169–172 (2007)

    Article  Google Scholar 

  45. Samudrala, R., Moult, J.: A graph-theoretic algorithm for comparative modeling of protein structure. J. Mol. Biol. 279(1), 287–302 (1998)

    Article  Google Scholar 

  46. 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)

    Article  MathSciNet  MATH  Google Scholar 

  47. 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)

    Article  MathSciNet  MATH  Google Scholar 

  48. Wasserman, S., Pattison, P.: Logit models and logistic regressions for social networks: I. An introduction to Markov graphs and p*. Psychometrika 61(3), 401–425 (1996)

    Google Scholar 

  49. Wood, D.R.: On the maximum number of cliques in a graph. Graphs and Combinatorics 23(3), 337–352 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  50. Zaki, M.J., Parthasarathy, S., Ogihara, M., Li, W.: New algorithms for fast discovery of association rules. In: Proc. 3rd Int. Conf. Knowledge Discovery and Data Mining, pp. 283–286. AAAI Press, Menlo Park (1997), http://www.aaai.org/Papers/KDD/1997/KDD97-060.pdf

    Google Scholar 

  51. Zomorodian, A.: The tidy set: a minimal simplicial set for computing homology of clique complexes. In: Proc. 26th ACM Symp. Computational Geometry, pp. 257–266 (2010), http://www.cs.dartmouth.edu/~afra/papers/socg10/tidy-socg.pdf

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of California, Irvine, USA

    David Eppstein, Maarten Löffler & Darren Strash

Authors
  1. David Eppstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maarten Löffler
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Darren Strash
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, KAIST, Gwahangno 335, 305-701, Yuseong-gu, Daejeon, Korea

    Otfried Cheong  & Kyung-Yong Chwa  & 

  2. School of Computer Science and Engineering, Seoul National University, 151-742, Seoul, Korea

    Kunsoo Park

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Eppstein, D., Löffler, M., Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6506. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-17517-6_36

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-17516-9

  • Online ISBN: 978-3-642-17517-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation