cs.DS
Safety in s t Paths, Trails and Walks. Given a directed graph G and a pair of nodes s and t , an emph s t bridge 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 emph safe with respect to a set mathcal W of s t walks, if W is a subwalk of all walks in mathcal W . We start by considering the maximal safe walks when mathcal W consists of all s t paths, all s t trails, or all s t walks of G . We show that the first two problems are immediate linear time generalisations of finding all s t bridges, while the third problem is more involved. 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. We further generalise these problems, by assuming that safety is defined only with respect to a subset of emph 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 emph s t articulation 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.