{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:35:30Z","timestamp":1782970530249,"version":"3.54.5"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"European Unions Horizon 2020 research and innovation program","award":["853109"],"award-info":[{"award-number":["853109"]}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021_184735"],"award-info":[{"award-number":["200021_184735"]}],"id":[{"id":"10.13039\/501100001711","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":[[2025,10,31]]},"abstract":"\n We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of vertices. Roughly speaking, the method can transform fractional\/probabilistic label assignments of the vertices into integral\/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). The method unifies and significantly generalizes prior work on deterministic local rounding techniques [Ghaffari, Kuhn FOCS\u201921; Harris FOCS\u201919; Fischer, Ghaffari, Kuhn FOCS\u201917; Fischer DISC\u201917] to obtain polylogarithmic-time deterministic distributed solutions for combinatorial graph problems. Our general rounding result enables us to locally and efficiently derandomize a range of distributed algorithms for local graph problems, including maximal independent set (MIS), maximum-weight independent set approximation, and minimum-cost set cover approximation. As highlights, we, in particular, obtain the following results.\n \n \n \u2014<\/jats:label>\n \n We obtain a deterministic\n \n \\(O(\\log^{2}\\Delta\\cdot\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -round algorithm for computing an MIS in the\n \n \\(\\mathsf{LOCAL}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n model and an almost as efficient\n \n \\(O(\\log^{2}\\Delta\\cdot\\log\\log\\Delta\\cdot\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -round deterministic MIS algorithm in the\n \n \\(\\mathsf{CONGEST}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n model. As a result, the best known deterministic distributed time complexity of the four most widely studied distributed symmetry breaking problems (MIS, maximal matching,\n \n \\((\\Delta+1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -vertex coloring, and\n \n \\((2\\Delta-1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -edge coloring) is now\n \n \\(O(\\log^{2}\\Delta\\cdot\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Our new MIS algorithm is also the first direct polylogarithmic-time deterministic distributed MIS algorithm, which is not based on network decomposition.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n We obtain efficient deterministic distributed algorithms for rounding fractional solutions for maximum (weighted) independent set and minimum (weighted) set cover. In particular, for any constant\n \n \\(\\varepsilon > 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we give a deterministic\n \n \\(O(\\log^{2}\\Delta+\\log^{*}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -round algorithm for computing an independent set of size\n \n \\((1\/2-\\varepsilon)\\,{\\cdot}\\,n\/\\deg_{\\mathrm{avg}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and we give deterministic\n \n \\(O(\\log^{2}(\\Delta W)+\\log^{*}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -round algorithms for computing a\n \n \\((1-\\varepsilon)\/\\Delta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation of maximum weight independent set, and for computing a\n \n \\((1-\\varepsilon)\/r\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation of maximum weight matching in hypergraphs of rank\n \n \\( r \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . For minimum set cover instances with sets of size at most\n \n \\( s \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and where each element is contained in at most\n \n \\( t \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n sets, we show that an\n \n \\(O(\\log s)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation can be computed in time\n \n \\(O(\\log s\\cdot\\log^{2}t+\\log^{*}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1145\/3742476","type":"journal-article","created":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T09:09:51Z","timestamp":1748941791000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3372-7853","authenticated-orcid":false,"given":"Salwa","family":"Faour","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4213-9898","authenticated-orcid":false,"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, Massachusetts,USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1057-9429","authenticated-orcid":false,"given":"Christoph","family":"Grunau","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1025-5037","authenticated-orcid":false,"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9646-8446","authenticated-orcid":false,"given":"V\u00e1clav","family":"Rozho\u0148","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.89"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835797"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993825"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_2_9_2","first-page":"437","volume-title":"Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC)","author":"Barenboim L.","year":"2018","unstructured":"L. Barenboim, M. Elkin, and U. Goldenberg. 2018. Locally-iterative distributed \\((\\Delta+1)\\) -coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), 437\u2013446."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00376-1"},{"key":"e_1_3_2_12_2","first-page":"471","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC)","author":"Chang Yi-Jun","year":"2019","unstructured":"Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. 2019. The complexity of ( \\({\\Delta}\\) + 1) coloring in congested clique, massively parallel computation, and centralized local computation. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 471\u2013480."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331626"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(82)90004-8"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0344-4"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585243"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_23_2","first-page":"1009","volume-title":"Proceedings of the 62nd IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Ghaffari M.","year":"2021","unstructured":"M. Ghaffari and F. Kuhn. 2021. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proceedings of the 62nd IEEE Symposium on Foundations of Computer Science (FOCS), 1009\u20131020."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90003-5"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.181"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523693"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00048"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_30"},{"key":"e_1_3_2_31_2","first-page":"35:1","volume-title":"Proceedings of the 34th Symposium on Distributed Computing (DISC)","author":"Kawarabayashi K.","year":"2020","unstructured":"K. Kawarabayashi, S. Khoury, A. Schild, and G. Schwartzman. 2020. Improved distributed approximations for maximum independent set. In Proceedings of the 34th Symposium on Distributed Computing (DISC), 35:1\u201335:16."},{"key":"e_1_3_2_32_2","first-page":"35:1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC)","author":"Kawarabayashi K.","year":"2018","unstructured":"K. Kawarabayashi and G. Schwartzman. 2018. Adapting local sequential algorithms to the distributed setting. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), 35:1\u201335:17."},{"key":"e_1_3_2_33_2","volume-title":"Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Kuhn F.","year":"2009","unstructured":"F. Kuhn. 2009. Local weak coloring algorithms and implications on deterministic symmetry breaking. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109666"},{"key":"e_1_3_2_35_2","first-page":"394","volume-title":"Proceedings of the 22nd Symposium on Distributed Computing (DISC)","author":"Lenzen C.","year":"2008","unstructured":"C. Lenzen and R. Wattenhofer. 2008. Leveraging linial\u2019s locality limit. In Proceedings of the 22nd Symposium on Distributed Computing (DISC), 394\u2013407."},{"key":"e_1_3_2_36_2","first-page":"331","volume-title":"Proceedings of the 28th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"N. Linial","year":"1987","unstructured":"N. Linial. 1987. Distributive graph algorithms \u2013 Global solutions from local data. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science (FOCS), 331\u2013335."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90033-S"},{"key":"e_1_3_2_40_2","first-page":"16:1","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC)","author":"Maus Y.","year":"2020","unstructured":"Y. Maus and T. Tonoyan. 2020. Local conflict coloring revisited: Linial for lists. In Proceedings of the 34th International Symposium on Distributed Computing (DISC), 16:1\u201316:18."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/1280283.1280327"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_44_2","first-page":"223","volume-title":"Proceedings of the Innovations in Theoretical Computer Science (ITCS)","author":"Rubinfeld Ronitt","year":"2011","unstructured":"Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. 2011. Fast local computation algorithms. In Proceedings of the Innovations in Theoretical Computer Science (ITCS), 223\u2013238."},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0166-218X(02)00205-6","article-title":"A note on greedy algorithms for maximum weighted independent set problem","volume":"126","author":"Yamazaki K.","year":"2003","unstructured":"K. Yamazaki, S. Sakai, and M. Togasaki. 2003. A note on greedy algorithms for maximum weighted independent set problem. Discrete Applied Mathematics 126 (2003), 313\u2013322.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_46_2","first-page":"436","article-title":"On an external problem in graph theory","volume":"48","author":"Tur\u00e1n P.","year":"1941","unstructured":"P. Tur\u00e1n. 1941. On an external problem in graph theory. Matematikai \u00e9s Fisikai Lapok 48 (1941), 436\u2013452.","journal-title":"Matematikai \u00e9s Fisikai Lapok"},{"key":"e_1_3_2_47_2","unstructured":"V. K. Wei. 1981. A Lower Bound on the Stability Number of a Simple Graph. Technical Report No. 81-11217-9. Bell Laboratories Technical Memorandum."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3742476","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T15:51:52Z","timestamp":1757346712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3742476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3742476"],"URL":"https:\/\/doi.org\/10.1145\/3742476","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2023-07-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}