{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T07:02:09Z","timestamp":1773558129426,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100002341","name":"Research Council of Finland","doi-asserted-by":"crossref","award":["346968, 358744"],"award-info":[{"award-number":["346968, 358744"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["ERC, SCALEBIO, 101169716"],"award-info":[{"award-number":["ERC, SCALEBIO, 101169716"]}],"id":[{"id":"10.13039\/501100000780","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":[[2026,4,30]]},"abstract":"\n Cut arcs<\/jats:italic>\n , or\n strong bridges<\/jats:italic>\n , are one of the most fundamental reachability notions in directed graphs. Specifically, in a strongly connected graph\n \n \\(G=(V,E)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (\n \n \\(|V|=n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n \\(|E|=m\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ), a\n cut arc<\/jats:italic>\n is an arc\n \n \\(e\\in E\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for which there exist\n \n \\(u,v\\in V\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that all\n \n \\( u \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n \\( v \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n walks contain\n \n \\( e \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n In this article, we generalise this notion to\n cut paths<\/jats:italic>\n , that is, walks\n \n \\( W \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for which there exist\n \n \\(u,v\\in V\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that all\n \n \\( u \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n \\( v \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n walks contain\n \n \\( W \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n as subwalk. We first prove various properties of cut paths and define their\n remainder structure<\/jats:italic>\n , which we use to present a simple\n \n \\(O(m)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -time verification algorithm for a cut path. We further show that a graph contains at most\n \n \\(O(n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n maximal cut paths of length at most\n \n \\(O(n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n each, and present an\n optimal<\/jats:italic>\n \n \\(O(n^{2})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n enumeration algorithm for maximal cut paths.\n <\/jats:p>\n \n We apply cut paths and their remainder structure to improve several reachability problems from bioinformatics, as follows. A walk is called\n safe<\/jats:italic>\n if it is a subwalk of every node-covering closed walk of a strongly connected graph.\n Multi-safety<\/jats:italic>\n is defined analogously, by considering node-covering\n sets<\/jats:italic>\n of closed walks instead. Cut paths provide\n simple<\/jats:italic>\n \n \\(O(m)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -time algorithms verifying if a walk is safe or multi-safe. Further, by simultaneous computation of remainder structures of all subwalks of a cut path in linear time, we can identify all maximal multi-safe walks in\n \n \\(O(mn)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time. This improves over the state-of-the-art algorithm running in time\n \n \\(O(m^{2}+n^{3}\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1145\/3790095","type":"journal-article","created":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T14:47:28Z","timestamp":1769179648000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cut Paths and Their Remainder Structure"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7247-756X","authenticated-orcid":false,"given":"Massimo","family":"Cairo","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9352-0088","authenticated-orcid":false,"given":"Shahbaz","family":"Khan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2387-0952","authenticated-orcid":false,"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Verona, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4878-2809","authenticated-orcid":false,"given":"Sebastian","family":"Schmidt","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5302-0580","authenticated-orcid":false,"given":"Elia C.","family":"Zirondelli","sequence":"additional","affiliation":[{"name":"University of Trento, Trento, Italy and University of Verona, Verona, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,4]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-018-0122-7"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106421"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2022.30"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00877-w"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2023.17"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341731"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632176"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90049-3"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.10.003"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2968448"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.007"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1258530"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603052"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.11.011"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3077584.3077589"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0005"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.276601.122"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2016.0141"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2019.0828"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3790095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T06:44:33Z","timestamp":1773557073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3790095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,4]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3790095"],"URL":"https:\/\/doi.org\/10.1145\/3790095","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,4]]},"assertion":[{"value":"2024-03-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}