{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:45Z","timestamp":1750309365508,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sponsor Israel Science Foundation","award":["552\/16 and 2084\/18"],"award-info":[{"award-number":["552\/16 and 2084\/18"]}]},{"name":"Sponsor Len Blavatnik and the Blavatnik Family foundation, and the Sponsor Simons Foundation","award":["825876"],"award-info":[{"award-number":["825876"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"\n In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a vertex pair\n \n \\((s,t)\\in V(G)\\times V(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and a set of edge faults\n \n \\(F\\subseteq E(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a replacement path\n \n \\(P(s,t,F)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is an\n \n \\(s\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n \\(t\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n shortest path in\n \n \\(G\\setminus F\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . For integer parameters\n \n \\(L,f\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a\n replacement path covering<\/jats:italic>\n (\n \n \\(\\mathsf{RPC}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) is a collection of subgraphs of\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , denoted by\n \n \\(\\mathcal{G}_{L,f}=\\{G_{1},\\ldots,G_{r}\\}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that for every set\n \n \\(F\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of at most\n \n \\(f\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n faults (i.e.,\n \n \\(|F|\\leq f\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) and every replacement path\n \n \\(P(s,t,F)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of at most\n \n \\(L\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n edges, there exists a subgraph\n \n \\(G_{i}\\in\\mathcal{G}_{L,f}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n that contains all the edges of\n \n \\(P\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and does not contain any of the edges of\n \n \\(F\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The covering value of the\n \n \\(\\mathsf{RPC}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n \n \\(\\mathcal{G}_{L,f}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is then defined to be the number of subgraphs in\n \n \\(\\mathcal{G}_{L,f}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n In the randomized setting, it is easy to build an\n \n \\((L,f)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n \\(\\mathsf{RPC}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with covering value of\n \n \\(O(\\max\\{L,f\\}^{\\min\\{L,f\\}}\\cdot\\min\\{L,f\\}\\cdot \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , but to this date, there is no efficient\n deterministic<\/jats:italic>\n algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following:\n \n \n \u2014<\/jats:label>\n \n There exist efficient deterministic constructions of\n \n \\((L,f)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n \\(\\mathsf{RPC}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call\n HM<\/jats:italic>\n hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed\u2013Solomon codes and Algebraic-Geometric codes.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n For every\n \n \\(L,f\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , there exists an\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -vertex graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n whose\n \n \\((L,f)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n \\(\\mathsf{RPC}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n covering value is\n \n \\(\\Omega(L^{f})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant breadth first search (BFS) structures.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n An application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon et al. (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts.<\/jats:p>","DOI":"10.1145\/3673760","type":"journal-article","created":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T09:30:45Z","timestamp":1718703045000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Replacement Path Covering"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"given":"Karthik","family":"C. S.","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2357-2445","authenticated-orcid":false,"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267781"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90161-5"},{"key":"e_1_3_3_4_2","first-page":"12:1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919)","author":"Alon Noga","year":"2019","unstructured":"Noga Alon, Shiri Chechik, and Sarel Cohen. 2019. Deterministic combinatorial replacement paths and distance sensitivity oracles. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919). 12:1\u201312:14."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798607"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150334.1150336"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940874"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.123"},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","unstructured":"Greg Bodwin Michael Dinitz and Caleb Robelle. 2020. Optimal vertex fault-tolerant spanners in polynomial time. DOI: https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551794","DOI":"10.1137\/1.9781611976465.174"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/2781925.2782542"},{"key":"e_1_3_3_12_2","first-page":"25:1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP \u201920)","author":"Chakraborty Diptarka","year":"2020","unstructured":"Diptarka Chakraborty and Keerti Choudhary. 2020. New extremal bounds for reachability and strong-connectivity preservers under failures. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP \u201920). 25:1\u201325:20."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384253"},{"key":"e_1_3_3_14_2","first-page":"1479","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chechik Shiri","year":"2017","unstructured":"Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. 2017. (1+\u220a)-approximate f-sensitive distance oracles. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1479\u20131496."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/090758039"},{"key":"e_1_3_3_16_2","first-page":"33:1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP \u201920)","author":"Chuzhoy Julia","year":"2020","unstructured":"Julia Chuzhoy, Merav Parter, and Zihan Tan. 2020. On packing low-diameter spanning trees. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP \u201920). 33:1\u201333:18."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993830"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405735"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00291-2"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0605009"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1996.0147"},{"issue":"3","key":"e_1_3_3_23_2","first-page":"24","article-title":"A new class of linear correcting codes","volume":"6","author":"Goppa Valerii Denisovich","year":"1970","unstructured":"Valerii Denisovich Goppa. 1970. A new class of linear correcting codes. Problemy Peredachi Informatsii 6, 3 (1970), 24\u201330.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365835"},{"key":"e_1_3_3_25_2","unstructured":"Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2019. Essential Coding Theory. Retrieved from http:\/\/www.cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","unstructured":"Yael Hitron and Merav Parter. 2020. Round-efficient distributed byzantine computation. DOI: 10.48550\/arXiv.2004.06436","DOI":"10.48550\/arXiv.2004.06436"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492475"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001280"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767408"},{"key":"e_1_3_3_30_2","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing","author":"Parter Merav","year":"2019","unstructured":"Merav Parter. 2019a. Small cuts and connectivity certificates: A fault tolerant approach. In Proceedings of the 33rd International Symposium on Distributed Computing."},{"key":"e_1_3_3_31_2","unstructured":"Merav Parter. 2019b. Small cuts and connectivity certificates: A fault tolerant approach. Retrieved from https:\/\/arxiv.org\/abs\/1908.03022"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520047"},{"issue":"1","key":"e_1_3_3_33_2","first-page":"1\u201311:24","article-title":"Sparse fault-tolerant BFS structures","volume":"13","author":"Parter Merav","year":"2016","unstructured":"Merav Parter and David Peleg. 2016. Sparse fault-tolerant BFS structures. ACM Transactions on Algorithms 13, 1 (2016), 11:1\u201311:24.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310536"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331620"},{"issue":"2","key":"e_1_3_3_36_2","first-page":"300\u2013304","article-title":"Polynomial codes over certain finite fields","volume":"8","author":"Reed Irving S.","year":"1960","unstructured":"Irving S. Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics (SIAM) 8, 2 (1960), 300\u2013304.","journal-title":"Journal of the Society for Industrial and Applied Mathematics (SIAM)"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.945244"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1964.1053661"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19821090103"},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1109\/FOCS.2019.00034","volume-title":"Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS \u201919)","author":"Brand Jan van den","year":"2019","unstructured":"Jan van den Brand and Thatchaphol Saranurak. 2019. Sensitive distance and reachability oracles for large batch updates. In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS \u201919). IEEE, 424\u2013435."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3068"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438646"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.20"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3673760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:08Z","timestamp":1750291568000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3673760"],"URL":"https:\/\/doi.org\/10.1145\/3673760","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"assertion":[{"value":"2023-05-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}