{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T21:13:46Z","timestamp":1784236426214,"version":"3.55.0"},"reference-count":29,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T00:00:00Z","timestamp":1697500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Federman Cyber Security Center at the Hebrew University of Jerusalem","award":["PE0000006"],"award-info":[{"award-number":["PE0000006"]}]},{"name":"#NEXTGENERATIONEU (NGEU)","award":["PE0000006"],"award-info":[{"award-number":["PE0000006"]}]},{"name":"Ministry of University and Research (MUR)","award":["PE0000006"],"award-info":[{"award-number":["PE0000006"]}]},{"name":"National Recovery and Resilience Plan (NRRP)","award":["PE0000006"],"award-info":[{"award-number":["PE0000006"]}]},{"name":"MNESYS","award":["PE0000006"],"award-info":[{"award-number":["PE0000006"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>The maximum independent set problem is a classic and fundamental combinatorial challenge, where the objective is to find the largest subset of vertices in a graph such that no two vertices are adjacent. In this paper, we introduce a novel linear prioritized local algorithm tailored to address this problem on random d-regular graphs with a small and fixed degree d. Through exhaustive numerical simulations, we empirically investigated the independence ratio, i.e., the ratio between the cardinality of the independent set found and the order of the graph, which was achieved by our algorithm across random d-regular graphs with degree d ranging from 5 to 100. Remarkably, for every d within this range, our results surpassed the existing lower bounds determined by theoretical methods. Consequently, our findings suggest new conjectured lower bounds for the MIS problem on such graph structures. This finding has been obtained using a prioritized local algorithm. This algorithm is termed \u2018prioritized\u2019 because it strategically assigns priority in vertex selection, thereby iteratively adding them to the independent set.<\/jats:p>","DOI":"10.3390\/computation11100206","type":"journal-article","created":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T10:43:10Z","timestamp":1697539390000},"page":"206","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Large Independent Sets on Random d-Regular Graphs with Fixed Degree d"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2311-4380","authenticated-orcid":false,"given":"Raffaele","family":"Marino","sequence":"first","affiliation":[{"name":"Dipartimento di Fisica e Astronomia, Universit\u00e0 degli Studi di Firenze, Via Giovanni Sansone 1, Sesto Fiorentino, 50019 Firenze, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Scott","family":"Kirkpatrick","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University of Jerusalem, Edmond Safra Campus, Givat Ram, Jerusalem 91904, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,10,17]]},"reference":[{"key":"ref_1","unstructured":"Cook, S. (2006). The Millennium Prize Problems, American Mathematical Society."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1137\/0206038","article-title":"Finding a maximum independent set","volume":"6","author":"Tarjan","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","article-title":"Exact algorithms for maximum independent set","volume":"255","author":"Xiao","year":"2017","journal-title":"Inf. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Mezard, M., and Montanari, A. (2009). Information, Physics, and Computation, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"ref_5","unstructured":"Mohseni, M., Eppens, D., Strumpfer, J., Marino, R., Denchev, V., Ho, A.K., Isakov, S.V., Boixo, S., Ricci-Tersenghi, F., and Neven, H. (2021). Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization. arXiv."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"12996","DOI":"10.1038\/ncomms12996","article-title":"The backtracking survey propagation algorithm for solving random K-SAT problems","volume":"7","author":"Marino","year":"2016","journal-title":"Nat. Commun."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/s10915-022-02044-x","article-title":"Solving non-linear Kolmogorov equations in large dimensions by using deep learning: A numerical comparison of discretization schemes","volume":"94","author":"Marino","year":"2023","journal-title":"J. Sci. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"035032","DOI":"10.1088\/2632-2153\/ac0496","article-title":"Learning from survey propagation: A neural network for MAX-E-3-SAT","volume":"2","author":"Marino","year":"2021","journal-title":"Mach. Learn. Sci. Technol."},{"key":"ref_9","unstructured":"Bomze, I.M., Budinich, M., Pardalos, P.M., and Pelillo, M. (1999). Handbook of Combinatorial Optimization, Springer."},{"key":"ref_10","unstructured":"Karp, R.M. (1972). Complexity of Computer Computations, Springer."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3671","DOI":"10.1038\/s41598-023-30391-8","article-title":"Hard optimization problems have soft edges","volume":"13","author":"Marino","year":"2023","journal-title":"Sci. Rep."},{"key":"ref_12","unstructured":"Wein, A.S. (2020). Optimal Low-Degree Hardness of Maximum Independent Set. arXiv."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., and Sudan, M. (2014, January 12\u201314). Limits of local algorithms over sparse random graphs. Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, Princeton, NJ, USA.","DOI":"10.1145\/2554797.2554831"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1214\/16-AOP1094","article-title":"Local algorithms for independent sets are half-optimal","volume":"45","author":"Rahman","year":"2017","journal-title":"Ann. Probab."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s11511-017-0145-9","article-title":"Maximum independent sets on random regular graphs","volume":"217","author":"Ding","year":"2016","journal-title":"Acta Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1090\/S0002-9939-1981-0624948-6","article-title":"The independence ratio of regular graphs","volume":"83","year":"1981","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_17","first-page":"179","article-title":"lndependent sets in regular graphs of high girth","volume":"23","author":"McKay","year":"1987","journal-title":"Ars Comb."},{"key":"ref_18","unstructured":"Balogh, J., Kostochka, A., and Liu, X. (2017). Cubic graphs with small independence ratio. arXiv."},{"key":"ref_19","first-page":"012021","article-title":"The hard-core model on random graphs revisited","volume":"Volume 473","author":"Barbier","year":"2013","journal-title":"Proceedings of the ELC International Meeting on Inference, Computation, and Spin Glasses (ICSG2013)"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s10955-022-03062-7","article-title":"Improved replica bounds for the independence ratio of random regular graphs","volume":"190","author":"Harangi","year":"2023","journal-title":"J. Stat. Phys."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","article-title":"Differential equations for random processes and random graphs","volume":"5","author":"Wormald","year":"1995","journal-title":"Ann. Appl. Probab."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0012-365X(83)90273-X","article-title":"A note on the independence number of triangle-free graphs","volume":"46","author":"Shearer","year":"1983","journal-title":"Discret. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0012-365X(03)00241-3","article-title":"Analysis of greedy algorithms on graphs with bounded degrees","volume":"273","author":"Wormald","year":"2003","journal-title":"Discret. Math."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5236","DOI":"10.1016\/j.tcs.2009.08.025","article-title":"Large independent sets in random regular graphs","volume":"410","author":"Duckworth","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1002\/rsa.20547","article-title":"Invariant Gaussian processes and independent sets on regular graphs of large girth","volume":"47","author":"Harangi","year":"2015","journal-title":"Random Struct. Algorithms"},{"key":"ref_26","unstructured":"Cs\u00f3ka, E. (2016). Independent sets and cuts in large-girth regular graphs. arXiv."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"013302","DOI":"10.1103\/PhysRevE.100.013302","article-title":"Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs","volume":"100","author":"Angelini","year":"2019","journal-title":"Phys. Rev. E"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1007\/s00493-016-3236-x","article-title":"Local algorithms, regular graphs of large girth, and random regular graphs","volume":"38","author":"Hoppen","year":"2018","journal-title":"Combinatorica"},{"key":"ref_29","unstructured":"Bishop, C.M. (2006). Pattern Recognition and Machine Learning, Springer."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/10\/206\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:08:37Z","timestamp":1760130517000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/10\/206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,17]]},"references-count":29,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["computation11100206"],"URL":"https:\/\/doi.org\/10.3390\/computation11100206","relation":{},"ISSN":["2079-3197"],"issn-type":[{"value":"2079-3197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,17]]}}}