Document Open Access Logo

Greedy Maximal Independent Sets via Local Limits

Authors Michael Krivelevich , Tamás Mészáros , Peleg Michaeli , Clara Shikhelman

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.20.pdf
  • Filesize: 0.62 MB
  • 19 pages

Document Identifiers

Author Details

Michael Krivelevich
  • School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 6997801, Israel
Tamás Mészáros
  • Fachbereich Mathematik und Informatik, Institut für Mathematik, Freie Universität Berlin, 14195 Berlin, Germany
Peleg Michaeli
  • School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 6997801, Israel
Clara Shikhelman
  • Simons Institute for the Theory of Computing, Berkeley, CA, USA
  • School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 6997801, Israel

Funding

  • Krivelevich, Michael: Partially supported by USA - Israel BSF grants 2014361 and 2018267, and by ISF grant 1261/17.
  • Mészáros, Tamás: Research supported by the Dahlem Research School and by the Berlin Mathematics Research Center Math+.
  • Michaeli, Peleg: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement number 676970, RANDGEOM).

Acknowledgements

The authors wish to thank the organisers of the Joint FUB - TAU Workshop on Graph and Hypergraph Colouring, hosted by the Freie Universität Berlin in 2018, and Michal Amir, Shagnik Das, Lior Gishboliner, Matan Harel, Frank Mousset, Matan Shalev and Yinon Spinka for useful discussions and ideas.

Cite AsGet BibTex

Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman. Greedy Maximal Independent Sets via Local Limits. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.AofA.2020.20

Abstract

The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science - and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge. In this paper we present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to study new ones, such as random trees. We conclude our work by analysing the random greedy algorithm more closely when the base graph is a tree. We show that in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Greedy maximal independent set
  • random graph
  • local limit

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. David Aldous. Asymptotic fringe distributions for general families of random trees. The Annals of Applied Probability, 1(2):228-266, 1991. URL: http://links.jstor.org/sici?sici=1050-5164(199105)1:2<228:AFDFGF>2.0.CO;2-8&origin=MSN.
  2. David Aldous and J. Michael Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 1-72. Springer, Berlin, 2004. URL: https://doi.org/10.1007/978-3-662-09444-0_1.
  3. Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. Electronic Journal of Probability, 6:no. 23, 13, 2001. URL: https://doi.org/10.1214/EJP.v6-96.
  4. Patrick Bennett and Tom Bohman. A note on the random greedy independent set algorithm. Random Structures & Algorithms, 49(3):479-502, 2016. URL: https://doi.org/10.1002/rsa.20667.
  5. Paola Bermolen, Matthieu Jonckheere, and Pascal Moyal. The jamming constant of uniform random graphs. Stochastic Processes and their Applications, 127(7):2138-2178, 2017. URL: https://doi.org/10.1016/j.spa.2016.10.005.
  6. Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, and Julian Shun. Internally deterministic parallel algorithms can be fast. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, pages 181-192, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2145816.2145840.
  7. Tom Bohman. The triangle-free process. Advances in Mathematics, 221(5):1653-1677, 2009. URL: https://doi.org/10.1016/j.aim.2009.02.018.
  8. Tom Bohman and Peter Keevash. Dynamic concentration of the triangle-free process. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, volume 16 of CRM Series, pages 489-495. Ed. Norm., Pisa, 2013. URL: https://doi.org/10.1007/978-88-7642-475-5_78.
  9. Béla Bollobás and Paul Erdős. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 80(3):419-427, 1976. URL: https://doi.org/10.1017/S0305004100053056.
  10. Béla Bollobás and Mykhaylo Tyomkyn. Walks and paths in trees. Journal of Graph Theory, 70(1):54-66, 2012. URL: https://doi.org/10.1002/jgt.20600.
  11. Graham Brightwell, Svante Janson, and Malwina Luczak. The greedy independent set in a random graph with given degrees. Random Structures & Algorithms, 51(4):565-586, 2017. URL: https://doi.org/10.1002/rsa.20716.
  12. Péter Csikvári. On a poset of trees. Combinatorica, 30(2):125-137, 2010. URL: https://doi.org/10.1007/s00493-010-2516-0.
  13. Herold G. Dehling, Sjoert R. Fleurke, and Christof Külske. Parking on a random tree. Journal of Statistical Physics, 133(1):151-157, 2008. URL: https://doi.org/10.1007/s10955-008-9589-9.
  14. Paul Erdős, Stephen Suen, and Peter Winkler. On the size of a random maximal graph. In Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, "Random Graphs '93" (Poznań, 1993), volume 6(2-3), pages 309-318, 1995. URL: https://doi.org/10.1002/rsa.3240060217.
  15. James W. Evans. Random and cooperative sequential adsorption. Reviews of modern physics, 65(4):1281, 1993. Google Scholar
  16. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, 1996. URL: https://doi.org/10.1145/226643.226652.
  17. Steven R. Finch. Mathematical constants, volume 94 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2003. Google Scholar
  18. Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy MIS. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2152-2160. SIAM, Philadelphia, PA, 2018. URL: https://doi.org/10.1137/1.9781611975031.140.
  19. Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris. The triangle-free process and the Ramsey number R(3,k). arXiv e-prints, February 2013. URL: http://arxiv.org/abs/1302.6279.
  20. Paul J. Flory. Intramolecular reaction between neighboring substituents of vinyl polymers. Journal of the American Chemical Society, 61(6):1518-1521, 1939. URL: https://doi.org/10.1021/ja01875a053.
  21. Dave Freedman and Larry Shepp. An Unfriendly Seating Arrangement. SIAM Review, 4(2):150-150, April 1962. URL: https://doi.org/10.1137/1004037.
  22. David Gamarnik and David A. Goldberg. Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections. Combinatorics, Probability and Computing, 19(1):61-85, 2010. URL: https://doi.org/10.1017/S0963548309990186.
  23. David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. The Annals of Probability, 45(4):2353-2376, 2017. URL: https://doi.org/10.1214/16-AOP1114.
  24. Geoffrey R. Grimmett. Random labelled trees and their branching networks. Australian Mathematical Society. Journal. Series A, 30(2):229-237, 1980/81. Google Scholar
  25. Geoffrey R. Grimmett and Colin J. H. McDiarmid. On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 77:313-324, 1975. URL: https://doi.org/10.1017/S0305004100051124.
  26. Hamed Hatami, László Lovász, and Balázs Szegedy. Limits of locally-globally convergent graph sequences. Geometric and Functional Analysis, 24(1):269-296, 2014. URL: https://doi.org/10.1007/s00039-014-0258-7.
  27. Jan Hladký, Asaf Nachmias, and Tuan Tran. The local limit of the uniform spanning tree on dense graphs. Journal of Statistical Physics, 173(3-4):502-545, 2018. URL: https://doi.org/10.1007/s10955-017-1933-5.
  28. Carlos Hoppen and Nicholas Wormald. Properties of regular graphs with large girth via local algorithms. Journal of Combinatorial Theory. Series B, 121:367-397, 2016. URL: https://doi.org/10.1016/j.jctb.2016.07.009.
  29. Carlos Hoppen and Nicholas Wormald. Local algorithms, regular graphs of large girth, and random regular graphs. Combinatorica, 38(3):619-664, 2018. URL: https://doi.org/10.1007/s00493-016-3236-x.
  30. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pages 85-103. Plenum, New York, 1972. Google Scholar
  31. Alexander K. Kelmans. On graphs with randomly deleted edges. Acta Mathematica Academiae Scientiarum Hungaricae, 37(1-3):77-88, 1981. URL: https://doi.org/10.1007/BF01904874.
  32. Valentin F. Kolchin. Branching processes, random trees, and a generalized scheme of arrangements of particles. Mathematical notes of the Academy of Sciences of the USSR, 21(5):386-394, 1977. URL: https://doi.org/10.1007/BF01788236.
  33. Joseph Lauer and Nicholas C. Wormald. Large independent sets in regular graphs of large girth. Journal of Combinatorial Theory. Series B, 97(6):999-1009, 2007. URL: https://doi.org/10.1016/j.jctb.2007.02.006.
  34. Russell Lyons, Robin Pemantle, and Yuval Peres. Conceptual proofs of Llog L criteria for mean behavior of branching processes. The Annals of Probability, 23(3):1125-1138, 1995. URL: http://links.jstor.org/sici?sici=0091-1798(199507)23:3<1125:CPOLCF>2.0.CO;2-Y&origin=MSN.
  35. Colin J. H. McDiarmid. Colouring random graphs. Annals of Operations Research, 1(3):183-200, 1984. URL: https://doi.org/10.1007/BF01874388.
  36. Amram Meir and John W. Moon. The expected node-independence number of random trees. Nederlandse Akademie van Wetenschappen. Proceedings. Series A. Indagationes Mathematicae, 76:335-341, 1973. Google Scholar
  37. Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 327-336, October 2008. URL: https://doi.org/10.1109/FOCS.2008.81.
  38. Ewan S. Page. The distribution of vacancies on a line. Journal of the Royal Statistical Society. Series B., 21:364-374, 1959. URL: http://links.jstor.org/sici?sici=0035-9246(1959)21:2<364:TDOVOA>2.0.CO;2-1&origin=MSN.
  39. Ilona Palásti. On some random space filling problems. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5:353-359, 1960. Google Scholar
  40. Mathew D. Penrose and Aidan Sudbury. Exact and approximate results for deposition and annihilation processes on graphs. The Annals of Applied Probability, 15(1B):853-889, 2005. URL: https://doi.org/10.1214/105051604000000765.
  41. Michael E. Picollelli. The final size of the C_𝓁-free process. SIAM Journal on Discrete Mathematics, 28(3):1276-1305, 2014. URL: https://doi.org/10.1137/110824097.
  42. Mustazee Rahman and Bálint Virág. Local algorithms for independent sets are half-optimal. The Annals of Probability, 45(3):1543-1577, 2017. URL: https://doi.org/10.1214/16-AOP1094.
  43. Alfréd Rényi. On a one-dimensional problem concerning random space filling. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 3:109-127, 1958. Google Scholar
  44. Aidan Sudbury. Random sequential adsorption on random trees. Journal of Statistical Physics, 136(1):51-58, 2009. URL: https://doi.org/10.1007/s10955-009-9776-3.
  45. Lutz Warnke. The C_𝓁-free process. Random Structures & Algorithms, 44(4):490-526, 2014. URL: https://doi.org/10.1002/rsa.20468.
  46. Lutz Warnke. When does the K₄-free process stop? Random Structures & Algorithms, 44(3):355-397, 2014. URL: https://doi.org/10.1002/rsa.20444.
  47. Lutz Warnke. On Wormald’s differential equation method. arXiv e-prints, May 2019. URL: http://arxiv.org/abs/1905.08928.
  48. Nicholas C. Wormald. Differential equations for random processes and random graphs. The Annals of Applied Probability, 5(4):1217-1235, 1995. URL: http://links.jstor.org/sici?sici=1050-5164(199511)5:4<1217:DEFRPA>2.0.CO;2-A&origin=MSN.
  49. Nicholas C. Wormald. The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms, pages 73-155. Polish Scientific Publishers PWN, 1999. Google Scholar
  50. Nicholas C. Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239-298. Cambridge Univ. Press, Cambridge, 1999. Google Scholar
  51. Nicholas C. Wormald. Analysis of greedy algorithms on graphs with bounded degrees. Discrete Mathematics, 273(1-3):235-260, 2003. EuroComb'01 (Barcelona). URL: https://doi.org/10.1016/S0012-365X(03)00241-3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact