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\in E\) for which there exist \(u,v\in V\) , such that all \( u \) - \( v \) walks contain \( e \) . In this article, we generalise this notion to cut paths , that is, walks \( W \) for which there exist \(u,v\in 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}\log n)\) .

genomes. Our modified algorithms lead to a substantial improvement in alignment-based contiguity, with negligible additional computational costs and either no or a small increase in the number of misassemblies.

In a strongly connected graph $G = (V,E)$, a cut arc (also called strong bridge) is an arc $e \in E$ whose removal makes the graph no longer strongly connected. Equivalently, there exist $u,v \in 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 \in 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. 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. These properties yield an $O(mn)$ algorithm outputting all maximal multi-safe walks, improving over the state-of-the-art algorithm running in time $O(m^2+n^3)$. 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.

Abstract Given a directed graphGand a pair of nodessandt, ans-tbridgeofGis an edge whose removal breaks alls-tpaths ofG(and thus appears in alls-tpaths). Computing alls-tbridges ofGis 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 walkWissafewith respect to a set $${\mathcal {W}}$$ W ofs-twalks, ifWis a subwalk of all walks in $${\mathcal {W}}$$ W . We start by considering the maximal safe walks when $${\mathcal {W}}$$ W consists of: alls-tpaths, alls-ttrails, or alls-twalks ofG. We show that the solutions for the first two problems immediately follow from finding alls-tbridges 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 ofvisibleedges. Here we prove a dichotomy between thes-tpaths ands-ttrails cases, and thes-twalks 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 ofs-tarticulation points(nodes appearing in alls-tpaths). 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.

Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G. Similarly, an s-t articulation point of G is a node whose removal breaks all s-t paths of G. Computing the sequence of all s-t bridges of G (as well as the s-t articulation points) is a basic graph problem, solvable in linear time using the classical min-cut algorithm (Ford and Fulkerson, 1956). We show a simplified and self-contained algorithm computing all s-t bridges and s-t articulation points of G, based on a single graph traversal from s to t avoiding an arbitrary s-t path, which is interrupted at the s-t bridges. Its proof of correctness uses simple inductive arguments, making the problem an application of merely graph traversal, rather than of the more complex maximum flow problem.

Due to the significant growth in passenger numbers, higher vehicle load factors and crowding become more and more of an issue in public transport. For safety reasons and because of an unsatisfactory discomfort, standing of passengers is rather limited in high-speed long-distance trains. In case of delays and (partially) cancelled trains, many passengers have to be rerouted. State-of-the-art rerouting merely focuses on minimizing delay at the destination of affected passengers but neglects limited vehicle capacities and crowding. Not considering capacities allows using highly efficient shortest path algorithms like RAPTOR or the connection scan algorithm (CSA). In this paper, we study the more complicated scenario where passengers compete for scarce capacities. This can be modeled as a piece-wise linear, convex cost multi-source multi-commodity unsplittable flow problem where each passenger group which has to be rerouted corresponds to a commodity. We compare a path-based integer linear programming (ILP) model with a heuristic greedy approach. In experiments with instances from German long-distance train traffic, we quantify the importance of considering vehicle capacities in case of train cancellations. We observe a tradeoff: The ILP approach slightly outperforms the greedy approach and both are much better than capacity unaware rerouting in quality, while the greedy algorithm runs more than three times faster.