2026-07-24T01:20:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17669 2024-03-06T11:00:16Z ddc:004 open_access

Cut Paths and Their Remainder Structure, with Applications Cairo, Massimo Khan, Shahbaz Rizzi, Romeo Schmidt, Sebastian Tomescu, Alexandru I. Zirondelli, Elia C. reachability cut arc strong bridge covering walk safety persistence essentiality genome assembly In a strongly connected graph G = (V,E), a cut arc (also called strong bridge) is an arc e ∈ E whose removal makes the graph no longer strongly connected. Equivalently, there exist u,v ∈ V, such that all u-v walks contain e. Cut arcs are a fundamental graph-theoretic notion, with countless applications, especially in reachability problems. In this paper we initiate the study of cut paths, as a generalisation of cut arcs, which we naturally define as those paths P for which there exist u,v ∈ V, such that all u-v walks contain P as subwalk. We first prove various properties of cut paths and define their remainder structures, which we use to present a simple O(m)-time verification algorithm for a cut path (|V| = n, |E| = m). Secondly, we apply cut paths and their remainder structures to improve several reachability problems from bioinformatics, as follows. A walk is called safe if it is a subwalk of every node-covering closed walk of a strongly connected graph. Multi-safety is defined analogously, by considering node-covering sets of closed walks instead. We show that cut paths provide simple O(m)-time algorithms verifying if a walk is safe or multi-safe. For multi-safety, we present the first linear time algorithm, while for safety, we present a simple algorithm where the state-of-the-art employed complex data structures. Finally we show that the simultaneous computation of remainder structures of all subwalks of a cut path can be performed in linear time, since they are related in a structured way. These properties yield an O(mn)-time algorithm outputting all maximal multi-safe walks, improving over the state-of-the-art algorithm running in time O(m²+n³). The results of this paper only scratch the surface in the study of cut paths, and we believe a rich structure of a graph can be revealed, considering the perspective of a path, instead of just an arc. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Massimo Cairo and Shahbaz Khan and Romeo Rizzi and Sebastian Schmidt and Alexandru I. Tomescu and Elia C. Zirondelli 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.17 urn:nbn:de:0030-drops-176690 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode