Safety in $s$-$t$ Paths, Trails and Walks
| Autor: | Alexandru I. Tomescu, Sebastian Stefan Schmidt, Massimo Cairo, Romeo Rizzi, Shahbaz Khan |
|---|---|
| Přispěvatelé: | Department of Computer Science, Algorithmic Bioinformatics, Bioinformatics |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Existential quantification 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Strong bridge Strong articulation point 01 natural sciences DOMINATORS Simple (abstract algebra) Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) PERSISTENCY ALGORITHM Representation (mathematics) Time complexity Mathematics Discrete mathematics 021103 operations research Ideal (set theory) Genome assembly Applied Mathematics Directed graph Graph algorithm 113 Computer and information sciences Computer Science Applications 010201 computation theory & mathematics Theory of computation Connectivity problem Graph (abstract data type) Safety |
| Zdroj: | Algorithmica |
| DOI: | 10.48550/arxiv.2007.04726 |
| Popis: | Given a directed graph G and a pair of nodes s and t, an s-tbridge of G is an edge whose removal breaks all s-t paths of G (and thus appears in all s-t paths). Computing all s-t bridges of G is a basic graph problem, solvable in linear time. In this paper, we consider a natural generalisation of this problem, with the notion of “safety” from bioinformatics. We say that a walk W is safe with respect to a set $${\mathcal {W}}$$ W of s-t walks, if W is a subwalk of all walks in $${\mathcal {W}}$$ W . We start by considering the maximal safe walks when $${\mathcal {W}}$$ W consists of: all s-t paths, all s-t trails, or all s-t walks of G. We show that the solutions for the first two problems immediately follow from finding all s-t 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 visible edges. Here we prove a dichotomy between the s-t paths and s-t trails cases, and the s-t 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 s-tarticulation points (nodes appearing in all s-t paths). We thus obtain the best possible results for natural “safety”-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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|