{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:50Z","timestamp":1750309130411,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T00:00:00Z","timestamp":1705881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS-2309958, CCF-2309708, DMS-1803325, CCF-2104795, and CCF-2143762"],"award-info":[{"award-number":["DMS-2309958, CCF-2309708, DMS-1803325, CCF-2104795, and CCF-2143762"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or\n            <jats:italic>graphlets<\/jats:italic>\n            ) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.\n          <\/jats:p>","DOI":"10.1145\/3632294","type":"journal-article","created":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T11:36:13Z","timestamp":1699616173000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast and Perfect Sampling of Subgraphs and Polymer Systems"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4675-2596","authenticated-orcid":false,"given":"Antonio","family":"Blanca","sequence":"first","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6510-4669","authenticated-orcid":false,"given":"Sarah","family":"Cannon","sequence":"additional","affiliation":[{"name":"Claremont McKenna College, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7937-7016","authenticated-orcid":false,"given":"Will","family":"Perkins","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105851"},{"key":"e_1_3_2_3_2","unstructured":"Konrad Anand Andreas G\u00f6bel Marcus Pappik and Will Perkins. 2023. Perfect sampling for hard spheres from strong spatial mixing. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201923) Vol. 275. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik Dagstuhl 38:1\u201338:18."},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","unstructured":"Konrad Anand and Mark Jerrum. 2022. Perfect sampling in infinite spin systems via strong spatial mixing. SIAM J. Comput. 51 4 (2022) 1280\u20131295.","DOI":"10.1137\/21M1437433"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1367696"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036107"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384271"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2414676.2414682"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01238860"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451042"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447397"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381177"},{"key":"e_1_3_2_16_2","unstructured":"Charles Carlson Ewan Davies and Alexandra Kolla. 2020. Efficient algorithms for the Potts model on small-set expanders. arXiv:2003.01154. Retrieved from https:\/\/arxiv.org\/abs\/2003.01154"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20968"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.87"},{"key":"e_1_3_2_20_2","first-page":"1307","volume-title":"2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Chen Zongchen","year":"2020","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2020. Rapid mixing of Glauber dynamics up to uniqueness via contraction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 1307\u20131318."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451035"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.13"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882603"},{"key":"e_1_3_2_25_2","unstructured":"Tobias Friedrich Andreas G\u00f6bel Martin S Krejca and Marcus Pappik. 2020. Polymer dynamics via cliques: New conditions for approximations. arXiv:2007.08293. Retrieved from https:\/\/arxiv.org\/abs\/2007.08293"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3470865"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2022.104894"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258627"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651334"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9469.00156"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00021"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch128"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","unstructured":"Tyler Helmuth Matthew Jenssen and Will Perkins. 2023. Finite-size scaling phase coexistence and algorithms for the random cluster model on random graphs. In Annales de l\u2019Institut Henri Poincare (B) Probabilites et statistiques Vol. 59. Institut Henri Poincar\u00e9 817\u2013848.","DOI":"10.1214\/22-AIHP1263"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-019-00928-y"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000080"},{"key":"e_1_3_2_38_2","volume-title":"Random Graphs","author":"Janson Svante","year":"2011","unstructured":"Svante Janson, Andrzej Rucinski, and Tomasz Luczak. 2011. Random Graphs. John Wiley & Sons."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1286669"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.24"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"issue":"2","key":"e_1_3_2_42_2","first-page":"3","article-title":"A generalization of the Catalan numbers","volume":"16","author":"Kahkeshani Reza","year":"2013","unstructured":"Reza Kahkeshani. 2013. A generalization of the Catalan numbers. Journal of Integer Sequences 16, 2 (2013), 3.","journal-title":"Journal of Integer Sequences"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth163"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211762"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.021"},{"key":"e_1_3_2_46_2","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201919)","author":"Liao Chao","year":"2019","unstructured":"Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. 2019. Counting independent sets and colorings on random regular bipartite graphs. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201919). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_13"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976236.64"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330995"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/235610.235641"},{"key":"e_1_3_2_51_2","first-page":"464","volume-title":"Proceedings of the Latin American Symposium on Theoretical Informatics","author":"Read-McFarland Andrew","year":"2021","unstructured":"Andrew Read-McFarland and Daniel \u0160tefankovi\u010d. 2021. The hardness of sampling connected subgraphs. In Proceedings of the Latin American Symposium on Theoretical Informatics. Springer, 464\u2013475."},{"key":"e_1_3_2_52_2","first-page":"488","volume-title":"Proceedings of the Artificial Intelligence and Statistics","author":"Shervashidze Nino","year":"2009","unstructured":"Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Proceedings of the Artificial Intelligence and Statistics. PMLR, 488\u2013495."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"issue":"1","key":"e_1_3_2_56_2","first-page":"93","article-title":"Fast simulation of new coins from old","volume":"15","author":"\u015eerban Nacu","year":"2005","unstructured":"Nacu \u015eerban and Peres Yuval. 2005. Fast simulation of new coins from old. The Annals of Applied Probability 15, 1A (2005), 93\u2013115.","journal-title":"The Annals of Applied Probability"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:56Z","timestamp":1750286996000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,22]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3632294"],"URL":"https:\/\/doi.org\/10.1145\/3632294","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,1,22]]},"assertion":[{"value":"2022-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}