Answers are grounded in this paper and cite their sources.
This research explores cut paths in directed graphs, revealing methods to improve reachability problems in bioinformatics.
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²)\) 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²+n³log n)\) .
No takes yet. Share an insight, caveat, or question.
Cairo et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: