Cut Paths and Their Remainder Structure, with Applications
| Autor: | Cairo, Massimo, Khan, Shahbaz, Rizzi, Romeo, Schmidt, Sebastian, Tomescu, Alexandru I., Zirondelli, Elia C. |
|---|---|
| Přispěvatelé: | Algorithmic Bioinformatics, Department of Computer Science, Bioinformatics, Berenbrink, Petra, Bouyer, Patricia, Dawar, Anuj, Kanté, Mamadou Moustapha |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
safety covering walk Discrete Mathematics (cs.DM) essentiality strong bridge persistence 113 Computer and information sciences Quantitative Biology - Quantitative Methods Theory of computation → Graph algorithms analysis Mathematics of computing → Paths and connectivity problems FOS: Biological sciences FOS: Mathematics genome assembly Mathematics - Combinatorics Combinatorics (math.CO) Applied computing → Computational biology Quantitative Methods (q-bio.QM) Computer Science - Discrete Mathematics reachability cut arc |
| Zdroj: | 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
| DOI: | 10.4230/lipics.stacs.2023.17 |
| Popis: | 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. LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 17:1-17:17 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|