{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T16:49:44Z","timestamp":1772729384710,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T00:00:00Z","timestamp":1634083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T00:00:00Z","timestamp":1634083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Helsinki including Helsinki University Central Hospital"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a directed graph<jats:italic>G<\/jats:italic>and a pair of nodes<jats:italic>s<\/jats:italic>and<jats:italic>t<\/jats:italic>, an<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic><jats:italic>bridge<\/jats:italic>of<jats:italic>G<\/jats:italic>is an edge whose removal breaks all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>paths of<jats:italic>G<\/jats:italic>(and thus appears in all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>paths). Computing all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>bridges of<jats:italic>G<\/jats:italic>is a basic graph problem, solvable in linear time. In this paper, we consider a natural generalisation of this problem, with the notion of \u201csafety\u201d from bioinformatics. We say that a walk<jats:italic>W<\/jats:italic>is<jats:italic>safe<\/jats:italic>with respect to a set<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {W}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>W<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>of<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>walks, if<jats:italic>W<\/jats:italic>is a subwalk of all walks in<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {W}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>W<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We start by considering the maximal safe walks when<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {W}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>W<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>consists of: all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>paths, all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>trails, or all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>walks of<jats:italic>G<\/jats:italic>. We show that the solutions for the first two problems immediately follow from finding all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>bridges after incorporating simple characterisations. However, solving the third problem requires non-trivial techniques for incorporating its characterisation. In particular, we show that there exists a compact representation computable in linear time, that allows outputting all maximal safe walks in time linear in their length. Our solutions also directly extend to multigraphs, except for the second problem, which requires a more involved approach. We further generalise these problems, by assuming that safety is defined only with respect to a subset of<jats:italic>visible<\/jats:italic>edges. Here we prove a dichotomy between the<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>paths and<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>trails cases, and the<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>walks case: the former two are NP-hard, while the latter is solvable with the same complexity as when all edges are visible. We also show that the same complexity results hold for the analogous generalisations of<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic><jats:italic>articulation points<\/jats:italic>(nodes appearing in all<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>paths). We thus obtain the best possible results for natural \u201csafety\u201d-generalisations of these two fundamental graph problems. Moreover, our algorithms are simple and do not employ any complex data structures, making them ideal for use in practice.<\/jats:p>","DOI":"10.1007\/s00453-021-00877-w","type":"journal-article","created":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T18:12:56Z","timestamp":1634148776000},"page":"719-741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Safety in s-t Paths, Trails and Walks"],"prefix":"10.1007","volume":"84","author":[{"given":"Massimo","family":"Cairo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9352-0088","authenticated-orcid":false,"given":"Shahbaz","family":"Khan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2387-0952","authenticated-orcid":false,"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4878-2809","authenticated-orcid":false,"given":"Sebastian","family":"Schmidt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,13]]},"reference":[{"issue":"6","key":"877_CR1","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1137\/S0097539797317263","volume":"28","author":"S Alstrup","year":"1999","unstructured":"Alstrup, S., Harel, D., Lauridsen, P.W., Thorup, M.: Dominators in linear time. SIAM J. Comput. 28(6), 2117\u20132132 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"877_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.21832","volume":"73","author":"C Bazgan","year":"2019","unstructured":"Bazgan, C., Fluschnik, T., Nichterlein, A., Niedermeier, R., Stahlberg, M.: A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths. Networks 73(1), 23\u201337 (2019). https:\/\/doi.org\/10.1002\/net.21832","journal-title":"Networks"},{"issue":"4","key":"877_CR3","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1137\/070693217","volume":"38","author":"AL Buchsbaum","year":"2008","unstructured":"Buchsbaum, A.L., Georgiadis, L., Kaplan, H., Rogers, A., Tarjan, R.E., Westbrook, J.R.: Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput. 38(4), 1533\u20131573 (2008)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"877_CR4","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1145\/1065887.1065888","volume":"27","author":"AL Buchsbaum","year":"2005","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: Corrigendum: a new, simpler linear-time dominators algorithm. ACM Trans. Program. Lang. Syst. 27(3), 383\u2013387 (2005)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"877_CR5","doi-asserted-by":"crossref","unstructured":"Cairo, M., Khan, S., Rizzi, R., Schmidt, S., Tomescu, A.I., Zirondelli, E.: Computing all $$s$$-$$t$$ bridges and articulation points simplified. arXiv preprint (2020). arXiv:2006.15024","DOI":"10.1016\/j.dam.2021.08.026"},{"issue":"4","key":"877_CR6","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1145\/3341731","volume":"15","author":"M Cairo","year":"2019","unstructured":"Cairo, M., Medvedev, P., Acosta, N.O., Rizzi, R., Tomescu, A.I.: An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph. ACM Trans. Algorithms 15(4), 48 (2019). https:\/\/doi.org\/10.1145\/3341731","journal-title":"ACM Trans. Algorithms"},{"key":"877_CR7","unstructured":"Cairo, M., Rizzi, R., Tomescu, A.I., Zirondelli, E.C.: Genome assembly, from practice to theory: safe, complete and linear-time. Presented at the (2020). arXiv:2002.10498"},{"issue":"2","key":"877_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01194399","volume":"47","author":"K Cechl\u00e1rov\u00e1","year":"1998","unstructured":"Cechl\u00e1rov\u00e1, K.: Persistency in the assignment and transportation problems. Mat. Meth. OR 47(2), 243\u2013254 (1998). https:\/\/doi.org\/10.1007\/BF01194399","journal-title":"Mat. Meth. OR"},{"key":"877_CR9","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 3rd edn. MIT Press, London (2009)","edition":"3"},{"issue":"3","key":"877_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6377(94)90049-3","volume":"15","author":"M Costa","year":"1994","unstructured":"Costa, M.: Persistency in maximum cardinality bipartite matchings. Oper. Res. Lett. 15(3), 143\u2013149 (1994). https:\/\/doi.org\/10.1016\/0167-6377(94)90049-3","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"877_CR11","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1007\/s10878-010-9334-6","volume":"22","author":"M Costa","year":"2011","unstructured":"Costa, M., de Werra, D., Picouleau, C.: Minimum $$d$$-blockers and $$d$$-transversals in graphs. J. Comb. Optim. 22(4), 857\u2013872 (2011). https:\/\/doi.org\/10.1007\/s10878-010-9334-6","journal-title":"J. Comb. Optim."},{"key":"877_CR12","volume-title":"Graph theory, graduate texts in mathematics","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph theory, graduate texts in mathematics, vol. 173, 4th edn. Springer, Berlin (2010)","edition":"4"},{"key":"877_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canad. J. Math. 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-5","journal-title":"Canad. J. Math."},{"key":"877_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980). https:\/\/doi.org\/10.1016\/0304-3975(80)90009-2","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"877_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"877_CR16","doi-asserted-by":"publisher","DOI":"10.1201\/b16132","volume-title":"Handbook of graph theory","author":"JL Gross","year":"2013","unstructured":"Gross, J.L., Yellen, J., Zhang, P.: Handbook of graph theory, 2nd edn. Chapman & Hall\/CRC, London (2013)","edition":"2"},{"issue":"4","key":"877_CR17","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/0603052","volume":"3","author":"PL Hammer","year":"1982","unstructured":"Hammer, P.L., Hansen, P., Simeone, B.: Vertices belonging to all or to no maximum stable sets of a graph. SIAM J. Algebr. Discret. Methods 3(4), 511\u2013522 (1982). https:\/\/doi.org\/10.1137\/0603052","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"877_CR18","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2011.11.011","volume":"447","author":"GF Italiano","year":"2012","unstructured":"Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theor. Comput. Sci. 447, 74\u201384 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"877_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-scale algorithm design: biological sequence analysis in the era of high-throughput sequencing","author":"V M\u00e4kinen","year":"2015","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-scale algorithm design: biological sequence analysis in the era of high-throughput sequencing. Cambridge University Press, Cambridge (2015)"},{"issue":"1","key":"877_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-018-0122-7","volume":"13","author":"N Obscura Acosta","year":"2018","unstructured":"Obscura Acosta, N., M\u00e4kinen, V., Tomescu, A.I.: A safe and complete algorithm for metagenomic assembly. Algorith. Mol. Biol. 13(1), 3 (2018)","journal-title":"Algorith. Mol. Biol."},{"key":"877_CR21","doi-asserted-by":"crossref","unstructured":"Onodera, T., Sadakane, K., Shibuya, T.: Detecting superbubbles in assembly graphs. In: A.E. Darling, J.\u00a0Stoye (eds.) Algorithms in Bioinformatics. In: Proceedings 13th International Workshop, WABI 2013, Sophia Antipolis, France, September 2-4, 2013. Lecture Notes in Computer Science, vol. 8126, pp. 338\u2013348. Springer (2013)","DOI":"10.1007\/978-3-642-40453-5_26"},{"key":"877_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-070-4","volume-title":"The algorithm design manual","author":"SS Skiena","year":"2008","unstructured":"Skiena, S.S.: The algorithm design manual, 2nd edn. Springer, Berlin (2008)","edition":"2"},{"issue":"6","key":"877_CR23","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"RE Tarjan","year":"1974","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2(6), 160\u2013161 (1974)","journal-title":"Inf. Process. Lett."},{"key":"877_CR24","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00268499","volume":"6","author":"RE Tarjan","year":"1976","unstructured":"Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Inf. 6, 171\u2013185 (1976)","journal-title":"Acta Inf."},{"key":"877_CR25","doi-asserted-by":"publisher","unstructured":"Tomescu, A.I., Medvedev, P.: Safe and Complete Contig Assembly Via Omnitigs. In: Proceedings Research in Computational Molecular Biology - 20th Annual Conference, RECOMB 2016, Santa Monica, CA, USA, April 17-21, 2016, pp. 152\u2013163 (2016). https:\/\/doi.org\/10.1007\/978-3-319-31957-5_11","DOI":"10.1007\/978-3-319-31957-5_11"},{"issue":"6","key":"877_CR26","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1089\/cmb.2016.0141","volume":"24","author":"AI Tomescu","year":"2017","unstructured":"Tomescu, A.I., Medvedev, P.: Safe and complete contig assembly through omnitigs. J. Comput. Mol. Cell Biol. 24(6), 590\u2013602 (2017). https:\/\/doi.org\/10.1089\/cmb.2016.0141","journal-title":"J. Comput. Mol. Cell Biol."},{"issue":"13","key":"877_CR27","doi-asserted-by":"publisher","first-page":"4306","DOI":"10.1016\/j.disc.2009.01.006","volume":"309","author":"R Zenklusen","year":"2009","unstructured":"Zenklusen, R., Ries, B., Picouleau, C., de Werra, D., Costa, M., Bentz, C.: Blockers and transversals. Discret. Math. 309(13), 4306\u20134314 (2009). https:\/\/doi.org\/10.1016\/j.disc.2009.01.006","journal-title":"Discret. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00877-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00877-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00877-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,11]],"date-time":"2023-11-11T02:56:01Z","timestamp":1699671361000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00877-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,13]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["877"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00877-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,13]]},"assertion":[{"value":"3 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}