{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:45:48Z","timestamp":1782971148292,"version":"3.54.5"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/W005573\/1"],"award-info":[{"award-number":["EP\/W005573\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The\n            <jats:italic>coalescence time<\/jats:italic>\n            is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as that of Cooper et\u00a0al., the coalescence time for graphs, such as binary trees,\n            <jats:italic>d<\/jats:italic>\n            -dimensional tori, hypercubes, and, more generally, vertex-transitive graphs, remains unresolved.\n          <\/jats:p>\n          <jats:p>\n            We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), the coalescence time of\n            <jats:italic>n<\/jats:italic>\n            random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we prove a tight worst-case bound for the coalescence time of\n            <jats:italic>\n              O(n\n              <jats:sup>3<\/jats:sup>\n              )\n            <\/jats:italic>\n            . By duality, our results yield identical bounds on the voter model.\n          <\/jats:p>\n          <jats:p>Our techniques also yield a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill.<\/jats:p>","DOI":"10.1145\/3576900","type":"journal-article","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T11:51:20Z","timestamp":1673956280000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2300-4819","authenticated-orcid":false,"given":"Varun","family":"Kanade","sequence":"first","affiliation":[{"name":"University of Oxford and The Alan Turing Institute, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0363-8547","authenticated-orcid":false,"given":"Frederik","family":"Mallmann-Trenn","sequence":"additional","affiliation":[{"name":"King\u2019s College London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0882-283X","authenticated-orcid":false,"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"University of Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(91)90090-Y"},{"key":"e_1_3_3_3_2","unstructured":"D. Aldous and J. Fill. 2002. Reversible Markov Chains and Random Walks on Graphs. Unpublished monograph. Retrieved January 23 2023 from http:\/\/www.stat.berkeley.edu\/ aldous\/RWG\/book.html."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3388392.3388402"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000125"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411510"},{"issue":"4","key":"e_1_3_3_8_2","first-page":"922","article-title":"Collisions of random walks","volume":"48","author":"Barlow Martin","year":"2012","unstructured":"Martin Barlow, Yuval Peres, and Perla Sousi. 2012. Collisions of random walks. Annales de l\u2019 Institut Henri Poincare 48, 4 (2012), 922\u2013946.","journal-title":"Annales de l\u2019 Institut Henri Poincare"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.27"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch46"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087817"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.146"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048273"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008693"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/120900368"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_37"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48653-5_17"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-642-02930-1_33","volume-title":"Automata, Languages and Programming","author":"Cooper Colin","year":"2009","unstructured":"Colin Cooper, Alan Frieze, and Tomasz Radzik. 2009. Multiple random walks and interacting particle systems. In Automata, Languages and Programming, Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas (Eds.). Springer, Berlin, Germany, 399\u2013410."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103428478"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/1958171.1958176"},{"key":"e_1_3_3_21_2","article-title":"Fast plurality consensus in regular expanders","volume":"1605","author":"Cooper Colin","year":"2016","unstructured":"Colin Cooper, Tomasz Radzik, Nicol\u00e1s Rivera, and Takeharu Shiraga. 2016. Fast plurality consensus in regular expanders. CoRR abs\/1605.08403 (2016). http:\/\/arxiv.org\/abs\/1605.08403.","journal-title":"CoRR"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0406029"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991158"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831000012X"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989516"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_36"},{"key":"e_1_3_3_27_2","article-title":"Efficient k-party voting with two choices","volume":"1602","author":"Els\u00e4sser Robert","year":"2016","unstructured":"Robert Els\u00e4sser, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. 2016. Efficient k-party voting with two choices. CoRR abs\/1602.04667 (2016). http:\/\/arxiv.org\/abs\/1602.04667.","journal-title":"CoRR"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_3_3_29_2","first-page":"1404","volume-title":"Proceedings of AAMAS","author":"Gauci Melvin","year":"2017","unstructured":"Melvin Gauci, Monica E. Ortiz, Michael Rubenstein, and Radhika Nagpal. 2017. Error cascades in collective behavior: A case study of the gradient algorithm on 1000 physical agents. In Proceedings of AAMAS. 1404\u20131412. http:\/\/dl.acm.org\/citation.cfm?id=3091319."},{"key":"e_1_3_3_30_2","article-title":"Tight analysis for the 3-majority consensus dynamics","volume":"1705","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Johannes Lengler. 2017. Tight analysis for the 3-majority consensus dynamics. CoRR abs\/1705.05583 (2017). http:\/\/arxiv.org\/abs\/1705.05583.","journal-title":"CoRR"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3088"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","unstructured":"Varun Kanade Frederik Mallmann-Trenn and Thomas Sauerwald. 2018. On coalescence time in graphs\u2014When is coalescing as fast as meeting?arxiv:cs.DM\/1611.02460.","DOI":"10.1137\/1.9781611975482.59"},{"key":"e_1_3_3_33_2","volume-title":"Proceedings of SODA","author":"Kanade Varun","year":"2019","unstructured":"Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. 2019. On coalescence time in graphs\u2014When is coalescing as fast as meeting? In Proceedings of SODA. http:\/\/arxiv.org\/abs\/1611.02460.A full version with all proofs is available at http:\/\/arxiv.org\/abs\/1611.02460."},{"key":"e_1_3_3_34_2","volume-title":"Markov Chains and Mixing Times","author":"Levin D.","year":"2006","unstructured":"D. Levin, Y. Peres, and E. Wilmer. 2006. Markov Chains and Mixing Times. American Mathematical Society."},{"issue":"3","key":"e_1_3_3_35_2","first-page":"849","article-title":"Chernoff-type bound for finite Markov chains","volume":"8","author":"Lezaud Pascal","year":"1989","unstructured":"Pascal Lezaud. 1989. Chernoff-type bound for finite Markov chains. Annals of Applied Probability 8, 3 (1989), 849\u2013867.","journal-title":"Annals of Applied Probability"},{"key":"e_1_3_3_36_2","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics, Paul Erd\u0151s Is Eighty 2 (1993), 1\u201346.","journal-title":"Combinatorics, Paul Erd\u0151s Is Eighty"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05523-6"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP813"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975505.13"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00055-X"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-013-0497-9"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062181"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3576900","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3576900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3576900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3576900"],"URL":"https:\/\/doi.org\/10.1145\/3576900","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,21]]},"assertion":[{"value":"2021-03-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}