Cut arcs, or strong bridges, are one of the most fundamental reachability notions in directed graphs. Specifically, in a strongly connected graph \ (G= (V, E) \) (\ (|V|=n\), \ (|E|=m\) ), a cut arc is an arc \ (e E\) for which there exist \ (u, v V\), such that all \ (u\) - \ (v\) walks contain \ (e\). In this paper we generalise this notion to cut paths, that is, walks \ (W\) for which there exist \ (u, v V\), such that all \ (u\) - \ (v\) walks contain \ (W\) as subwalk. We first prove various properties of cut paths and define their remainder structure, which we use to present a simple \ (O (m) \) -time verification algorithm for a cut path. We further show that a graph contains at most \ (O (n) \) maximal cut paths of length at most \ (O (n) \) each, and present an optimal \ (O (n^2) \) enumeration algorithm for maximal cut paths. We apply cut paths and their remainder structure 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. Cut paths provide simple \ (O (m) \) -time algorithms verifying if a walk is safe or multi-safe. Further, by simultaneous computation of remainder structures of all subwalks of a cut path in linear time, we can identify all maximal multi-safe walks in \ (O (mn) \) time. This improves over the state-of-the-art algorithm running in time \ (O (m^2+n^3 n) \).
Cairo et al. (Fri,) studied this question.