[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Solving maximum clique in sparse graphs: an \(O(nm+n2^{d/4})\) algorithm for \(d\)-degenerate graphs

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\). The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\). The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: Graph Partitioning and Graph Clustering, vol. 588. American Mathematical Society, Providence (2013)

  2. Bianconi, G., Marsili, M.: Emergence of large cliques in random scale-free networks. Europhys. Lett. 74(4), 740 (2006)

    Article  MathSciNet  Google Scholar 

  3. Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization, pp. 1–74. Springer, Berlin (1999)

  4. Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.M.: Fast algorithms for max independent set. Algorithmica. 62(1–2), 382–415 (2012)

    Google Scholar 

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

    Article  MATH  Google Scholar 

  6. Chung, F.: Graph theory in the information age. Notices AMS 57(6), 726–732 (2010)

    MATH  Google Scholar 

  7. Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Algorithms and Computation, pp. 403–414 (2010)

  8. Lick, D.R., White, A.T.: k-Degenerate graphs. Canad. J. Math 22, 1082–1096 (1970)

    Article  MATH  MathSciNet  Google Scholar 

  9. Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  10. Robson, J.M.: Finding a maximum independent set in time \({O}(2^{n/4})\). LaBRI, Université de Bordeaux I, Technical report (2001)

  11. Verma, A., Buchanan, A., Butenko, S.: Solving the maximum clique and vertex coloring problems on very large sparse networks. Working paper, Department of Industrial and Systems Engineering, Texas A &M University, College Station, TX (2012)

Download references

Acknowledgments

This material is based upon work supported by the AFRL Mathematical Modeling and Optimization Institute. Partial support by AFOSR under grants FA9550-12-1-0103 and FA8651-12-2-0011 is also gratefully acknowledged.

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Texas A&M University, 3131 TAMU, College Station, TX, 77843-3131, USA

    Austin Buchanan & Sergiy Butenko

  2. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville, FL, USA

    Jose L. Walteros & Panos M. Pardalos

Authors
  1. Austin Buchanan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jose L. Walteros
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sergiy Butenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Austin Buchanan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Buchanan, A., Walteros, J.L., Butenko, S. et al. Solving maximum clique in sparse graphs: an \(O(nm+n2^{d/4})\) algorithm for \(d\)-degenerate graphs. Optim Lett 8, 1611–1617 (2014). https://doi.org/10.1007/s11590-013-0698-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-013-0698-2

Keywords