Many Bioinformatics problems are based, at their core, on well-studied theoretical computational problems. For example biological sequence alignment involves computing the edit distance, or some approximation of it [17] . The progress on a Bioinformatics problem usually proceeds as follows: after initial heuristics or non-optimal approaches, a theoretical breakthrough comes along, which is so efficient theoretically that it is incorporated in all practical solutions for the problem, but is also further extended to better handle practical issues. A classical example is the problem of read mapping, i.e. locating occurrences of a short genomic string (a read ) inside a genome text. After initial approaches (e.g. based on hashing substrings of the text [41, 33] ), a major theoretical work [18] introduced the FM-index of a text, obtained by exploiting the theoretical compressibility (entropy) of the text. This has both theoretically provable performance guarantees as well as low index size, resulting in exceptional performance in practice. The FM-index is now at the core of all popular read mapping tools (e.g. [42, 40, 38] ) but is also enhanced with various theoretical models to handle errors, or mutations in the reads with respect to the genome text. Similar progress was witnessed also with other problems, such as phylogenetics which is addressed by e.g. major theoretical results on computing quartet distance [16, 62] . On the other hand, a theoretical breakthrough can also prove that the only hope for further progress on a Bioinformatics problem lies in better heuristics or approximations. Typically, this has been the case with only NP-hard problems, but recently the study of fine-grained complexity has also shown similar results for tractable problems. For example edit distance is not likely computable faster than quadratic time [2] , which thus also affects sequence alignment, a long-standing open problem in Bioinformatics.
However, despite this successful exchange of problems and results between Bioinformatics and Theoretical Computer Science, another flagship Bioinformatics problem, genome assembly, is generally lacking similar developments.
State-of-the-art in genome assembly. Given a collection of reads, the task is to reconstruct the source genome from which the reads were sequenced. This is one of the oldest problems in Bioinformatics [54] , whose formulations range from a shortest common superstring of the reads [54, 32, 31] , to various models of node-or arc-covering walks in different assembly graphs (encoding the overlaps between the reads, such as de Bruijn graphs [55] , or overlap graphs [48] ) [56, 46, 47, 30, 28, 51, 49] . In general, most such models of genome assembly are NP-hard. However, even if one approached such models via e.g. approximation algorithms (see the popular conjecture of whether there is a factor-2 approximation algorithm for the shortest common superstring problem [5]), a more fundamental issue in genome assembly is that such "global" problem formulations inherently admit a large number of solutions [35] , given the large size and complexity of the input data. In practice, genome assemblers output only shorter strings that are likely to be correct (i.e. are substrings of the source genome) [50, 43, 45] . Such a strategy commonly uses the assembly graph to find only the paths (unitigs) whose internal nodes have unit in-and out-degree. Since unitigs do not branch, their labels are correct and can be computed in linear time. The use of unitigs dates back to 1995 [31] and is at the core of most state-of-the-art genome assemblers, for both long reads (such as wtdbg2 [57] ), and short reads (such as MEGAHIT [39] ). Even though long reads are theoretically preferable, due to various practical limitations short reads are still used in many biomedical applications, such as the assembly of the SARS-CoV-2 genome [63] .
Over the years, there have been several attempts to generalize the notion of unitigs, while maintaining correctness from both theoretical and practical perspectives.
Surpassing the theoretical limitations using safe and complete algorithms. Despite being at the core of the state-of-the-art in both theory and practice, there is no reason why only 'unitigs' be the basis of correct partial answers to the genome assembly problem. In fact, various results [22, 6, 49, 58, 37, 7] presented the open question about the "assembly limit" (if any), or formally, what all can be correctly assembled from the input reads, by considering both graph theoretic and non-graph theoretic formulations. Unitigs were first generalized by [56] by considered the paths having internal nodes with unit out-degree (with no restriction on in-degree). These were later generalized [47, 29, 35] evolving the idea of correctness to the paths of the form P = P 1 eP 2 , such that e is an edge, the nodes of path P 1 have unit in-degree, and the nodes of path P 2 have unit out-degree (intuitively, P 1 is the only way to reach e, and P 2 is the only way e reaches other nodes). The question about the "assembly limit" was finally resolved in 2016 (around 20 years after unitigs were first introduced) in a major Bioinformatics venue [59] by introducing safe and complete algorithms for the problem, described as follows.
Given a solution to a problem (say some walk W in a graph), a partial solution (some subwalk of W ) is called safe if it appears in all solutions of the problem (is a subwalk of all solutions). An algorithm reporting only such safe partial solutions is called safe. A safe algorithm reporting all the safe partial solutions is called safe and complete. A safe and complete algorithm outputs exactly the parts of the source genome that can be correctly reconstructed. Notions similar to safety have also been earlier studied in Bioinformatics [60, 12, 50] , and in other fields, including persistence [24, 14, 11] , d-transversals [15] , d-blockers [64] , and most vital nodes and edges [4] .
Given an assembly graph, the most basic notion of a solution (or a source genome) is that of a walk covering all nodes or all arcs at least once, thereby explaining their existence in the assembly graph [59] . Even if the earlier works mentioned above on "global" genome assembly formulations include various shortest versions of such walks, it is widely acknowledged [49, 51, 45, 50, 43, 36] that a shortest walk misses repeats in the source genome. As such, [59] considered the genome assembly solution to be any closed node-or arc-covering walk of a graph. Trivially, their safe walks are also safe for shortest covering walks, and also include unitigs and their generalizations described above. They characterized all such safe walks as omnitigs [59] . On simulated error-free reads where the source genome is indeed a closed arc-covering walk, omnitigs were found to be on average 60% longer than unitigs, and to contain 60% more biological information without employing any heuristics Moreover, [59] presented an O(m 2 n)-time algorithm 1 finding all safe walks for such genome assembly solutions (referred to as omnitigs), in a graph with m arcs and n nodes. Later, Cairo et al. [9] improved this bound to O(mn), which they also proved to be optimal using worst-case graphs having Θ(mn)-sized solutions. Recently, Cairo et al.
[10] presented a linear-time outputsensitive algorithm for computing all maximal omnitigs, using a compact representation of the solution, called macrotigs. Since, for perfectly simulated reads, in practice the maximal omnitigs have the total length linear in the size of the graph [59, 9] , such an output sensitive algorithm is asymptotically equivalent to computing unitigs.
A limitation of the results from [59, 9, 1] is that safety is characterized in terms of forbidden structures. Hence, such characterizations in general give an easily verifiable NO certificate but not a similarly simple YES certificate. Nevertheless, these results essentially resolve the theoretical bottleneck of the genome assembly problem for perfect data, also showing that genome assembly is not as difficult as it has been believed, starting from the NP-hard formulations from the 1980s.
Practical limitations of genome assembly and of current safe and complete algorithms. The theoretical formulation of genome assembly using a single closed arc-covering walk uses the following assumptions. (i) All the reads are sequenced from a single circular genome, such that these reads have (ii) no errors, and (iii) no missing coverage (e.g. every position of the genome is covered by some read). However, these are very strong and impractical assumptions that are violated by almost all real input data. There are several reasons why assumption (i) is not always practical. When sequencing a bacterium [13] , one indeed obtains reads from a single circular genome. However, when sequencing all bacteria in an environmental sample (as in metagenomics [44] ), the reads originate from multiple circular genomes. In case of a virus [20] , the reads originate from a single linear genome. Finally, when sequencing eukaryotes such as human [8] , the reads originate from multiple linear chromosomes. Similarly, assumption (ii) is usually not practical because the sequencing process introduces errors in the reads, with error rates ranging from 1% for short reads, to 15% for long reads. Such read errors produce certain known structures of the assembly graph [50] , such as tips (short induced paths ending in a sink), and bubbles (two induced paths of the same length, and with the same endpoints, see also their generalization to superbubbles [25, 19, 53] ), which are usually handled in an initial error-correction stage using heuristics (e.g. tips are removed, and bubbles are popped by removing one of the parallel paths). Such bubbles can also arise from a correct read position in diploid genomes (such as human), but on which the mother's copy of the chromosome differs from the father's. Popping bubbles is favorable in this setting in order to obtain longer assemblies (since unitigs would otherwise be broken up by the endpoints of the bubble). Moreover, in a de Bruijn graph, arcs which appear very few times (having low abundance) in the input reads are heuristically removed, as they are assumed to be errors. But in practice, the assembly graph's topology might give evidence for the correctness of these arcs, especially in scenarios where low abundance is common [39] , so a more accurate removal strategy is likely to result in a better assembly. This applies even to state-of-the-art long read assemblers like wtdbg2 [57] which simply removes low abundance edges. Finally, assumption (iii) is also not always true due to the practical limitations of current sequencing technologies. Thus, since not all parts of the genome can always be read, even if the sample contains a single circular genome, the reads appear as if they were sequenced from multiple linear genomic sequences.
Most of these practical issues can be handled by considering more flexible theoretical formulations of the problem. Instead of always considering the solution to be a closed arc-covering walk of the assembly graph (used for single circular genome), we can change the model so that the solution is an arc-covering collection of k ≥ 2 closed walks (used for multiple circular genomes). A safe and complete algorithm for this problem has already been given by [1] . This was obtained also via a "forbidden paths" characterization, and then translated to an O(m 2 n)-time algorithm for finding all safe walks, only for k = ∞. Further, for addressing single linear genomes we further change the model so that the solution is an open arc-covering walk from a given node s to a given node t (s-t walk ), which can similarly be further changed to handle multiple linear chromosomes by considering the solution as an arc-covering collection of k ≥ 2 open s-t walks. The safe walks for the above models will be denoted as k-circular safe and k-st safe, respectively, and are formally defined as follows. Definition 1.1 (1-circular safe walk). Given a strongly connected graph, let C be the set of all circular walks which cover every arc of the graph. A walk is called 1-circular safe if it is a subwalk of every walk in C. Definition 1.2 (k-circular safe walk). Given a strongly connected graph, let C k be the set of all collections of exactly k circular walks which together cover every arc of the graph. A walk is called k-circular safe if it is a subwalk of some circular walk in every collection in C k . Figure 1 : Assume a "full" read coverage scenario in which reads of length at least 4 have been sequenced starting from each position a diploid genome (i.e. from both the mother and the father copy of a chromosome). An edge-centric de Bruijn graph of order 3 has all substrings of length 3 of the reads as nodes, and all substrings of length 4 as arcs (from their length-3 prefix to their length-3 suffix). The thin blue line depicts the mother genome as a walk in this graph. Orange marks a position in which the two haplotypes differ; this induces a bubble in the de Bruijn graph (dotted arcs). We assume that the red arcs have low abundance in the read dataset for some natural reasons despite being correct. But they would still be removed by current heuristic error-correction strategies, even though our models show evidence for their correctness. We set the dotted arcs to invisible, and model the genome as an s-t walk not required to cover the red and dotted arcs, where s = AAT and t = CGT. Below the mother's haplotype, we mark in green its maximal 1-st safe substrings. The thick safe walk of the mother's haplotype is also depicted in the graph (in green as well). We show in magenta the unitigs of the graph aligned to the mother haplotype. Additionally, the red parts of the unitigs would be missing if the red arcs were removed. Definition 1.3 (1-st safe walk). Given a graph with nodes s and t, let L be the set of all walks starting from s and ending in t, which cover every arc of the graph. A walk is called 1-st safe if it is a subwalk of every walk in L. Definition 1.4 (k-st safe walk). Given a graph with nodes s and t, let L k be the set of all collections of exactly k walks starting from s and ending in t, which together cover every arc of the graph. A walk is called k-st safe if it is a subwalk of some walk in every group in L k . Remark 1.5.
However, non-strongly connected graphs may admit multiple circular arc-covering walks, but require each disconnected component to be strongly connected. Hence we can assume the graph to be strongly connected, where we deal with each disconnected component separately.
2. For k = 1, k-circular safety and k-st safety reduce to 1-circular safety and 1-st safety respectively. If we consider collections with an arbitrary number of walks, then we refer to their safe walks as ∞-circular safe and ∞-st safe respectively.
Further, to handle errors and diploidy, instead of relying only on the heuristics as mentioned above, the theoretical models can be inherently extended to deal with such issues flexibly. For example, the models can be extended to require that the solution walk covers only a subset of the arcs (subset covering). The arcs not required to be covered can be those in tips, bubbles and those with low abundance in the reads. However, merely making them avoidable (and not removing them) can break the safety around such regions. Hence, another possible extension is to mark such parts of the graph as invisible (subset visibility), in the sense that such parts are invisible when we require that a safe walk appears in any solution walk. For example, marking bubbles as invisible prevents disrupting the safety of their flanking regions. See Figure 1 for an example of these models, which are formally defined as follows. Definition 1.6 (Subset covering). Given a graph with F ⊆ E, let C F k (or L F k ) be the set of all collections of exactly k circular (or s-t) walks which together cover every arc in F . A walk is Fcovering k-circular safe (or k-st safe) if it is a subwalk of some walk in every collection in C F k (or L F k ).
Definition 1.7 (Subset visible). Given a graph with F ⊆ E, let C k (or L k ) be the set of all groups of exactly k circular (or s-t) walks which together cover every arc in the graph. A walk is F -visible k-circular safe (or k-st safe) if its F -subsequence occurs contiguously in the F -subsequence of some walk in every collection in C k (or L k ), where the F -subsequence of a walk is obtained by removing its arcs not in F . Remark 1.8. We can also combine the subset covering and subset visibility models for some F, F ⊆ E, to get F -covering F -visible safe walks, for both circular and linear models. This also allows us to solve the same models in a node-centric formulation, where only (a subset of the) nodes are required to be covered and/or visible. This can be achieved using a simple transformation of the graph expanding each node to an arc and choosing only such node-arcs as the subset to be covered.
Given the improvements of omnitigs w.r.t. unitigs mentioned above for perfect data, we can assume that safe and complete algorithms for genome assembly models without using the assumptions (i)-(iii) can have a major impact in real genome assembly programs. Also, note that while [1] already gave an algorithm for finding ∞-circular safe walks, it was based on an appreciably different custom approach, and in general all results [1, 59, 9, 10] use problem specific techniques which are not extendable to other models. Thus, an eminent problem in this regard is to have a universal framework which addresses such models (single and multiple, circular and linear) efficiently, and is also flexible enough to adapt with such error correction techniques (subset covering and visibility) theoretically.
In this paper, we show that the theoretical assumptions (i)-(iii) used by state-of-the-art results can be avoided, overcoming the practical limitations of the theoretical breakthrough [59] for genome assembly. We obtain safe and complete algorithms for a plethora of genome assembly problems modeled as natural types of walks in a graph having theoretical significance. Moreover, we approach the problem with an entirely new perspective and introduce a universal framework, the hydrostructure of a walk, that can handle all such problem variants with a unified methodology. Our various algorithms show that the hydrostructure is easily adaptable to different problem variants, making it an ideal toolkit for handling various practical aspects of genome assembly. Even though the hydrostructure is developed mainly for such arc-covering models, it reveals a novel fundamental insight into the structure of a graph, which can be of independent interest. The technical contributions of our paper can be summarized as follows:
1. The Hydrostructure as a Universal Framework: We introduce the hydrostructure of a walk as a partition of a strongly connected graph from the perspective of a bridge-like walk. It identifies the parts of the graph separated by the walk, and gives a clear picture of the reachability among the remaining parts. As a result, it serves as a universal framework for an easy characterisation of problems that inherently rely on reachability, including the more prominent safety problems in genome assembly under arc-covering constraints.
The hydrostructure allows simpler characterizations for the known models of circular safe walks. For both single circular and ∞-circular safe walks, it presents an easily verifiable YES and NO certificate. For single circular walks, the previous characterizations identified forbidden paths [59, 9] resulting only in a NO certificate. For ∞-circular safe walks, the previous characterisation further required the presence of a certificate arc [1] forbidding cycles of certain types, resulting in a NO certificate which is harder to verify. However, the hydrostructure gives a complete characterisation of such problems, which is easily derivable using the components of the hydrostructure.
3. Characterization of New Models of Safety Problems: Using the hydrostructure, we are able to characterize new models of safety problems of potential practical significance for genome assembly. We characterise k-circular safe walks for any given k (where 1 < k < ∞), which was mentioned as an open problem in [1] , by proving the equivalence of the k-circular safe problems for all k ≥ 2. Further, we present the first characterizations for the single and multiple linear models (mentioned as open problems in [59] ). The linear models are in general harder to characterize because the location of s and t affects the safety of walks. However, such a characterisation, though not as simple, is naturally derivable from the components of the hydrostructure (except for the computation of a a minimum walk-cover of a certain size). Except for given k where it additionally requires computing the size of the minimum walk-cover 2 , and is limited to strongly connected graphs. Moreover, the flexibility of the hydrostructure allows us to study the above models in the more general settings of subset covering and subset visibility, making the solutions more tolerant to practical issues.
We also introduce the problem of verifying whether a given walk is safe in a model. Despite this problem not being explicitly studied earlier, the previous characterizations [59, 9, 1] resulted in O(mn) time verification algorithms, which again depend on the corresponding certificate for the model. Recently, Cairo et al.
[10] presented an algorithm which can be adapted to a linear-time verification algorithm for 1-circular safe walks, but it uses complex data structures. Our characterizations are directly adaptable to linear time optimal verification algorithms for almost all of our models, using simple techniques such as graph traversal. See Table 1 for a comparison.
Our verification algorithms can also be adapted to simple O(m 2 n) time algorithms (except for given k-st safe) to enumerate all the maximal safe walks. Further, using the optimal 1-circular safe algorithm [9] and our new characterisation, we not only improve upon [1] for ∞-circular walks, but also make our k-circular safe algorithm optimal. In order to improve our linear algorithms we present an alternate way to compute the hydrostructure for all subwalks of a walk simultaneously. Table 1 : A comparison of the previous results for safety problems with the new results trivially obtained from the characterisation, and the improved results. The size of the output is represented by o. The optimal algorithms are marked by * . The time bounds using a simple minimum walk cover algorithm are marked by # , which may be improved 3 with faster algorithms for computing the size of a minimum walk cover. The solution for this model ( # ) is also limited to strongly connected graphs. All the above models can also be extended to subset covering (see Appendix E) using the same bounds and to subset visibility (see Appendix F) with an additive O(mn) term.
(except for given k) by presenting a family of graphs having the size of all maximal safe walks Ω(mn). See Table 1 for a comparison.
As in the case of the FM-index, we believe the various results of this paper (handling different types of genomes, errors or complex regions, and missing coverage), can form the theoretical basis of future complete genome assemblers. As in the case of read mapping tools, our current results do have to be further enhanced with various practical heuristics. Also, notice that the hydrostructure is essentially a mathematical tool which is flexible for addressing a variety of models, is adaptable to develop simple yet efficient algorithms. Also, note that the output of all our algorithms is a subset of omnitigs (or their natural generalizations) solved by [10] using an optimal outputsensitive algorithm. Thus, we hope that our paper, together with [10] (in their current form or after further improvements) can help turn genome assembly into another success story of advanced theoretical results lying at the core of state-of-the-art genomic tools.
The main idea behind our approach is to distinguish between the reasons for the safety of a walk. In general, the primary and simplistic reason arises from the covering constraint, where every arc is individually safe. Further, every safe walk is extendable to both sides, along the only way to reach it (or its left wing), if it exists, and along the only way forward from it (or its right wing), if it exists. The secondary and more profound reason arises from the bridge-like nature of some walks, which means that they need to be contiguously traversed to reach from one part of the graph (source) to another part (target). Such a bridge-like characteristic of a walk is captured by the hydrostructure of a walk (terminology inspired by the water cycle on Earth [61] ), which distinguishes the source part as Sea and the target part as Cloud. The internal part of the bridge-like walk forms the Vapor, which is the only way water moves from Sea to Cloud. On the other hand, water can easily move from Cloud to Vapor and from Vapor to Sea. The residual part of the graph forms the River, which in general serves as an alternate route for the water from Cloud to Sea. For non-bridge-like walks the hydrostructure trivially reduces to Vapor being the entire graph, and the remaining components empty. For any given walk, we show that its hydrostructure and wings can be easily computed in linear time, by evaluating the restricted reachability of the end points of the walk.
The hydrostructure partitioning of the graph for a given walk results in interesting properties of reachability among the components of the hydrostructure. This gives a more structured overview of the graph from the perspective of the bridge-like walk. Using these explicit properties and clearer structure, it becomes easier to characterize the safety of bridge-like walks under different models. Moreover, we show that the hydrostructure is easily adaptable for practical applications by extending our solutions to more generic notions of safety resulting from subset covering and subset visibility models. In the former model, the previous characterisations are easily extendable. In the later model, the hydrostructure itself is generalizable, so that the existing characterizations can be directly applied without changes.
By computing the hydrostructure for a walk, it becomes much easier to characterize safety for the circular models. The characterization of the 1-circular safe model simplifies to merely Vapor not being the entire graph, which basically signifies that the walk is bridge-like. Notice that this characterization avoids forbidden paths as in [59, 9] resulting in easily verifiable YES and NO certificates. For the multiple-circular model an additional constraint includes having River non-empty. This characterisation drastically simplifies the previous result [1] , and is the same for any given number k ≥ 2 of closed walks (which was left open in [1] ). Further, both of these characterisations are directly adaptable to an optimal verification algorithms which report whether a given walk is safe, and enumeration algorithms for reporting all maximal circular safe walks. Moreover, using the optimal 1-circular safe enumeration algorithm [9] and the new characterisation, we also get an optimal k-circular safe enumeration algorithm.
The hydrostructure also allows us to obtain the first characterizations of safety for the single and multiple linear models. In these models, the presence of s and t in different components of the hydrostructure affects the safety of a walk (hence, even the wings are not trivially safe in this model). This results in a more complex case-based characterisations, but nevertheless based on the components of the hydrostructure, making them easy to verify. Surprisingly, every linear safe solution has to be 1-circular safe, which allows us to build the characterisation (and hence algorithms) of linear models on top of those for the single circular model. In the single linear model, River additionally has to be a single path, with some criteria based on the location of s and t. However, the multiple linear model generalizes the criteria on the River to be based on a minimum walk-cover of it of a certain size. Also, we require a separate characterisation for the safety of the wings, based on the reachability of s and t in the candidate walk. These characterizations are also adaptable to optimal (except for general k) verification algorithms and simple enumeration algorithms.
To improve the linear enumeration algorithms (to optimal for k = 1, ∞), we show that the hydrostructure can be maintained using an incremental computation. Since the linear characterisations are built on top of the 1-circular safe walks (computable in optimal time [9]), we incrementally compute the hydrostructure for all subwalks of a 1-circular safe walk. At its core, it uses the incremental reachability algorithm [26] requiring total O(m) for each 1-circular safe walk. Surprisingly every node and arc can enter and leave River exactly once during the incremental computation, allowing its maintenance in total O(m) time. This results in optimal k-st safe algorithms for k = 1, ∞, while for the rest it additionally checks if a subgraph can be covered with k walks.
Outline of the paper. We first describe the notation related to graph theory and safety in Section 2. Thereafter, the hydrostructure and its properties are described in Section 3. Applications of the hydrostructure for the circular and linear models are briefly presented in Section 4 (with details in Appendix B) and Section 5 (with details in Appendix C), respectively. Finally, we optimize our linear algorithms using the incremental computation of the hydrostructure in Section 6, and conclude our work in Section 7. In the interest of concise presentation, some proofs and implementation details are omitted and deferred to Appendix A and Appendix D, respectively. Moreover, the extensions of our characterisations to subset visibility and subset covering are deferred to Appendix F and Appendix E, respectively.
Graph Notations. A graph is a set G = V ∪ E, where V is a finite set of nodes, E is a finite multi-set of ordered pairs of nodes called arcs; given an arc e = (u, v), we say that u is the tail node tail(e) of e, and v is the head node head(e) of e. Self-loops are allowed. A strongly connected component (SCC) is a maximal subgraph that is strongly connected, i.e. for any two nodes x and y in the SCC, there exists a path from x to y. Similarly, a weakly connected component (WCC) is a maximal subgraph that is weakly connected, i.e., any two nodes x and y in the WCC are connected by an undirected path. A node is a source if it has no incoming arcs, and a sink if it has no outgoing arcs. For e ∈ E, we denote G \ e = (V, E \ {e}). In the rest of this paper, we assume a fixed strongly connected graph G = (V, E) which is not a cycle 4 , with |V | = n and |E| = m > n.
A w 1 -w walk (or simply walk ) in G is a non-empty alternating sequence of nodes and arcs
Deviating from standard terminology, if not otherwise indicated, w 1 and w are arcs. We call start(W ) = w 1 the start of W , and end(W ) = w the end of W . W is a path if it repeats no node or arc, except that start(W ) may equal end(W ). A walk W that contains at least two elements is bridge-like if there exist x, y ∈ G such that each x-y walk contains W , and otherwise it is called avertible. Observe that a bridge-like walk is an open path.
A walk W is called closed if start(W ) = end(W ) and > 1, otherwise it is open. The notation W W denotes the concatenation of walks W = (w 1 , . . . , w ) and W = (w 1 , . . . , w ), if (w 1 , . . . , w , w 1 , . . . , w ) is a walk. When writing a walk as a concatenation, then lower-case letters denote single nodes or arcs, i.e. aZb denotes the walk (a, z 1 , . . . , z , b) (where a and b are arcs). Subwalks of walks are defined in the standard manner, where subwalks of closed walks do not repeat the start/end if they run over the end. Additionally, a walk is a subwalk of a set of walks {W i }, if it is a subwalk of one W i .
A walk-cover of a graph is a set of walks that together cover all arcs of the graph, and its size is the number of walks. The minimum walk-cover (and hence its size) can be computed in O(mn) time using minimum flows, by reducing the problem to maximum flows (see e.g. [3]) and applying Orlin's and King's O(mn) time algorithms [52, 34] .
Safety Notations. We call a node v a join node (or split node) if its in-degree (or out-degree) is greater than 1. Similarly, an arc e is a join arc (or split arc) if head(e) is a join node (or tail(e) is a split node). Two arcs e and e are sibling arcs if head(e) = head(e ) or tail(e) = tail(e ). A walk W = (w 1 , . . . , w ) is univocal if at most w is a split node (if it is a node), and it is R-univocal if at most w 1 is a join node (if it is a node), and it is biunivocal if it is both univocal and R-univocal. Its univocal extension U (W ) is W l W W r where W l start(W ) is the longest R-univocal walk to start(W ) and start(W )W r is the longest univocal walk from end(W ).
For a walk W = w 1 , . . . , w let w i be its first join arc or w i = w 1 if W has no join arc, and let w j be its last split arc or w j = w if W has no split arc. If i ≥ j, then the trivial heart (or simply Figure 2 : A trivial walk on the left and a non-trivial walk on the right. The heart is colored green, the left wing violet and the right wing red. Note that the left wing is from arc to node and the right wing from node to arc. heart) Heart(W ) of W is its w j -w i subwalk, and otherwise the non-trivial heart (or simply heart) Heart(W ) is its w i -w j subwalk. A walk with a trivial heart is a trivial walk, and a walk with a non-trivial heart is a non-trivial walk. The left wing and right wing of W are W l and W r in the decomposition W l Heart(W )W r . See Figure 2 for a visualisation of these definitions.
Recall that in models in which a solution consists of k ≥ 2 walks, we say that a walk is safe if it appears as a subwalk of at least one walk in each solution.
Further, we use the following results from previous works in the literature. The first result was used in [1, 10] (and possibly other previous works) even though not stated explicitly. 
The hydrostructure of a walk partitions the strongly connected graph from the perspective of the walk; for a bridge-like walk it identifies two parts of the graph separated by the walk, and gives a clear picture of the reachability among the remaining parts. This allows an easy characterisation in problems (such as safety) that inherently rely on reachability. It is defined using the restricted forward and backward reachability for a walk, as follows.
Definition 3.1. The restricted forward and backward reachability of a walk W is defined as
By definition, all nodes and arcs of W (except for its last arc end(W ), since by our convention the walks start and end in an arc), are always in R + (W ) (and symmetrically for R − (W )). Further, if a walk is not bridge-like, we additionally have end(W ) ∈ R + (W ) as we will shortly prove, and R + (W ) extends to the entire graph G due to strong connectivity. Thus, inspired by the similarity between the water cycle on Earth and the reachability among the four parts of the Venn diagram of R + (W ) and R − (W ) (see Figure 3a ), we define the hydrostructure of a walk as follows.
Definition 3.2 (Hydrostructure of a Walk). Let W be a walk with at least two arcs.
• Figure 3 : (a): The partitioning of the hydrostructure of a non-trivial heart aZb in the four sets Sea, Cloud, Vapor, and River using R + (aZb) and R − (aZb). It also demonstrates the membership of the arcs, and the reachability among the parts. (b): Example of the hydrostructure for a trivial bridge-like walk aZb, with the sea-related and cloud-related SCC shown using thick green cycles. The River is a DAG of SCCs where the SCCs are blue cycles.
The reachability among the parts of the hydrostructure mimics the water cycle, which we describe as follows (formally proved later). For any node or arc in the Sea, the only way to reach the Cloud is by traversing the walk through the entire Vapor (similar to the evaporation process), as it is shared by both R + (W ) and R − (W ). Thus, for a bridge-like walk W , the hydrostructure exposes the Sea and the Cloud that are separated by W in the Vapor.
On the other hand, a node or an arc from the Cloud can directly reach the Vapor (by dissipation), being in R − (W ), and from the Vapor it can directly reach the Sea (by condensation), being in R + (W ). Finally, the River acts as an alternative path from the nodes and arcs in the Cloud to the Sea (by rainfall), since the forward reachability from the Cloud and the backward reachability from the Sea are not explored in R + (W ) and R − (W ).
Properties. The strong connectivity of the graph results in the hydrostructure of an avertible walk to have the entire graph as the Vapor, whereas the Sea, Cloud, and River are empty. On the other hand, for a bridge-like walk, the Vapor is exactly the internal path of the walk, resulting in the following important property for any walk W = aZb.
Note that the hydrostructure partitions not just the nodes but also the arcs of the graph. The strong connectivity of the graph and the definitions above result in the following properties of the parts of the hydrostructure (see Figure 3b for SCCs, and Figure 3a for Reachability).
Lemma 3.4. The hydrostructure on a bridge-like path aZb exhibits the following properties:
a. (Safety) Every walk from x ∈ Sea(aZb) to y ∈ Cloud(aZb) contains aZb as a subwalk. b. (Avoidance) Every x ∈ Cloud(aZb) and y ∈ Sea(aZb) have an x-y walk with no subwalk aZb. c. (Separation) a ∈ Sea(aZb) and b ∈ Cloud(aZb). e. (Reachability) Let (x, y) ∈ G × G be an ordered incidence pair (arc-node or node-arc) in G, where x and y are in different components of the hydrostructure of aZb. Then (x, y) can (only) be associated with the following pairs of components.
• (Vapor, Cloud) always where y = b, or (Sea, Vapor) always where x = a, • (Cloud, Vapor) or (Vapor, Sea), where both always occur for non-trivial aZb,
• (Cloud, River) or (River, Sea), where both always occur for nonempty River,
Implementation. To obtain the hydrostructure of a walk W , we need to compute R + (W ) (and symmetrically R − (W )). Note that R + (W ) for avertible walks is simply G, and for bridge-like walks is the graph traversal from start(W ) in G \ end(W ). We can identify if W is avertible while performing the traversal, by checking if the traversal reaches W again after leaving it. Thereafter, we can easily compute the Sea, Cloud, Vapor and River by processing each arc and node individually. The avertible walks can be identified more efficiently using Theorem 2.1 (c) as follows:
If W is avertible, then its only maximal bridge-like subwalks are W l Z and ZW r .
In the circular models the heart of a walk determines its safety, as the univocal extension of a safe walk is naturally safe. Therefore, every trivial walk is naturally safe because of the covering constraint for any arc in its heart, which can be univocally extended to get the whole walk. A non-trivial walk W with a bridge-like heart is safe as well, as every circular arc-covering walk contains all bridge-like walks by definition. If on the other hand Heart(W ) is avertible (having Vapor(W ) = G), then a walk can cover the entire graph without having Heart(W ) as subwalk, making it unsafe by definition. Thus, the characterisation for circular safe walks is succinctly described as follows (see Appendix B for the proofs of this section):
Theorem 4.1 (1-Circular). A non-trivial walk W is 1-circular safe iff Vapor(Heart(W )) is a path. Now, for k ≥ 2, a single circular arc-covering walk can be repeated to get k circular arccovering walks, implying that every k-circular safe walk is 1-circular safe. For the k-circular safety of a non-trivial walk W , an added issue (see Figure 4a ) is that two different circular walks can cover the sea and cloud-related strongly connected components. However, this is not possible if these components do not entirely cover the graph, i.e. the River is not empty. Thus, we get the following characterisation.
Theorem 4.2 (k-Circular). A non-trivial walk W is k-circular safe for k ≥ 2, iff Vapor(Heart(W )) is a path and River(Heart(W )) is non-empty.
Notice that our characterisation does not distinguish between k when k ≥ 2, implying that all the problems of (k ≥ 2)-circular safety are equivalent. These characterisations can be directly adapted for an optimal verification algorithm, by computing the hydrostructure for the given walk Figure 4 : (a) In the absence of the River, the two cycles (shown in thick green) can cover the cloud-related and sea-related SCCs of a non-trivial Heart without having aZb as subwalk. (b) The heart (green) and the wings (violet and red) of an avertible walk aZb. W is unsafe for s = s 1 and t = t 1 , because Heart(W ) is s 1 -t 1 suffix-prefix covered in W as it is part of the proper suffix of W starting from s 1 . W is safe for s = s 2 and t = t 2 , because the middle of Heart(W ) is not s 2 -t 2 suffix-prefix covered in W , since it is contained neither in the suffix starting in s 2 nor in the prefix ending in t 2 .
using the optimal O(mn) time 1-circular safe algorithm [9], the maximal k-circular safe walks can also be optimally enumerated in O(mn) time, by computing the hydrostructure for O(n) non-trivial 1-circular safe walks (Theorem 2.1 (b)) and using an interesting property of 1-circular safe walks that are not k-circular safe. See Appendix D.2 for more details on the implementation.
W is not k-circular safe then XaZ and ZbY are k-circular safe walks.
In this section we characterise the linear models for strongly connected graphs. In the corresponding appendix we also extend them to non-strongly connected graphs. Compared to the circular models, in the linear models the wings of a walk are not naturally safe, because s or t might occur in a wing. This allows a candidate solution to stop at s or t, covering the graph without having the entire wing as a subwalk. However, only a 1-circular safe walk W can be k-st safe. Otherwise, using an arc-covering closed walk that does not contain W , we can construct an arc-covering s-t walk by repeating the arc-covering walk, once starting from s and once ending at t.
We handle the wings of non-trivial k-st safe walks separately. Our characterisation has three conditions that force a walk to reach from Sea to Cloud of a bridge-like walk, and a fourth condition that makes only trivial walks safe. For a trivial walk, an additional sufficient condition for safety is if there is an arc in its heart that can only be covered by using the whole walk, i.e. it cannot be covered by using only a proper suffix starting in s or a proper prefix ending in t. Formally we say that an arc e in the heart of a trivial walk W is s-t suffix-prefix covered if it is part of a proper prefix of W that starts in s or part of a proper suffix of W that ends in t (see Figure 4b for an example). We get the following characterisation (see Appendix C for the proofs of this section).
Theorem 5.1 (k-st Safe Trivial Walks and Non-Trivial Hearts). A trivial walk W (or a non-trivial heart W ) is k-st safe iff it is a single arc or (a) River(W ) cannot be covered with k walks, or
Note that only 1-circular safe walks can fulfill this characterisation: a trivial walk is always 1-circular safe, and a non-trivial heart that is not 1-circular safe fulfills none of the four criteria.
Further, note that Condition (a) also makes the wings safe, since they are not in the River by Lemma 3.4 (d). Additionally if s is in the left wing, we can cover the prefix of the left wing before s without traversing the whole walk in two ways. Firstly, if the prefix before s is repeated in the suffix of the whole walk from s. Note that this case only happens if s is also in the heart, i.e. the left wing extends back into the heart, which makes the Sea of the heart a path and the River empty. Secondly, if t prematurely ends the traversal before covering the whole walk, i.e. t is present in the residual walk or the Sea. We get the following characterisation.
Theorem 5.2 (Wings of Non-Trivial k-st Safe Hearts). A non-trivial 1-circular safe walk W l W W r , where W is its heart, W l its left and W r its right wing, is k-st safe iff W is k-st safe and (a) River(W ) cannot be covered with k walks, or (b) either both of s ∈ W l and t ∈ W r are false, or exactly one is true with:
• if s ∈ W l , then t / ∈ R + (W ) ∪ W r and s / ∈ W , and
Note that the k-st safe problems are equivalent for all k ≥ m. Additionally, the maximal output size of the linear models is O(n 3 ). We can check a walk for k-st safety in O(m + f (m, n)) where f (m, n) is the time required to check the walk-cover. And using the two-pointer algorithm on each 1-circular safe walk, we can enumerate all maximal k-st safe walks in O(m 2 n + mnf (m, n)) time.
Recall from the preliminaries that f (m, n) ∈ O(mn), and further observe that for k ≥ m or k = 1 we get O(m). See Appendix D.3 for more details on the implementation.
We have earlier described the optimal verification algorithms for various safety models using the hydrostructure. However, to report all maximal linear safe solutions optimally, we additionally need a more efficient computation of the hydrostructure for all the relevant walks. This is achieved by incremental computation of R + (·), R − (·) and the River as follows.
Incremental Maintenance of Forward and Backwards Reachability. Because of symmetry it suffices to describe how to compute R + (W ). Consider that for a bridge-like walk aZb, R + (aZb) is aZ plus everything that is reachable from outgoing arcs of aZ other than b without entering aZ. This allows us to describe R + (aZb) as the union of subsets reachable from the outgoing siblings of arcs on Zb, denoted as the sibling reachability R + sib (e) of an arc e ∈ Zb, and formally defined as R + sib (e) := {x ∈ G | ∃ tail(e)-x walk in G \ e}. Formally we get the following. Lemma 6.1. Given a bridge-like walk aZb it holds that R + (aZb) = aZ ∪ arc e∈Zb R + sib (e). Additionally, since subwalks of bridge-like walks are bridge-like, the following allows us to compute R + sib (·) incrementally along a bridge-like walk. Lemma 6.2. Let aZb be a bridge-like walk where b is a split-arc and e a split-arc after a. Then (a) R + sib (e) ⊆ R + sib (b) and
Hence, we can compute all R + sib (·) using a single interrupted traversal. We number the nodes and arcs in W and then annotate each node and arc x with the first arc e ∈ W for which it is in R + sib (e). Afterwards we can decide if a node or arc x is in R + (aZb) of a given subwalk aZb by checking if x enters R + sib (·) before or with b, or if x ∈ aZ.
Incremental Maintenance of the River Properties. When using the two-pointer algorithm after computing the hydrostructure incrementally, we can maintain properties of the River used throughout the paper (Appendix E). By Lemma 6.2 each node and arc enters R + (·) (and leaves R − (·)) at most once during an execution of the two-pointer algorithm on a bridge-like walk. We can therefore sort the nodes and arcs of G into buckets in O(m) time according to when they enter and leave the River. The existence of the River can then be maintained in O(m) time for a complete execution of the two-pointer algorithm. Moreover, it is possible to maintain the in-degree and out-degree of each node and arc in the River as well as the number of sources (in-degree zero), sinks (out-degree zero) and violators (in-degree or out-degree at least two), and hence determine if the River is a path. Further, Lemma 6.2 also implies that entire SCCs of the River (using both R + sib (·) and R − sib (·)) enter and leave the River at most once during the execution of the two pointer algorithm. Hence, the SCCs of the River can also be identified in overall O(m) time. Finally, the size of a minimum walk-cover can also be maintained after each insertion or deletion of an edge from the River using the folklore fully dynamic update algorithm for maximum flows [23] in O(m) time per update. Since each edge enters and leaves the River at most once maintaining the size of the minimum walk-cover takes total O(m 2 ) time.
Applications. The above incremental computation techniques result in improving the O(m 2 n) term of runtimes of linear problems by a factor of m using amortization as follows. We execute the two-pointer algorithm on all maximal 1-circular safe walks (which we get in O(mn) time from [9]), but only maintain the hydrostructure and River properties for non-trivial and bridge-like trivial 1-circular safe walks (there are only O(n) of these by Theorem A.2 and they can be found in total O(mn) time by Theorem 3.6 (a)). For non-trivial 1-circular safe walks, instead of maintaining the hydrostructure for the whole walk, we maintain it for the heart. We describe how we handle trivial avertible walks in the same time bounds as non-trivial walks in Appendix D.4. Checking the walk-cover can be done as described above for k = 1 (maintain if the River is a path) or k ≥ m (always false) in O(m) time per maximal bridge-like walk. Recall that the output size is potentially larger than O(mn) resulting in the following. The runtimes of O(mn) are optimal because there exist a set of graphs (see Figure 5 ) with safe walks in each model of total length Ω(mn). As mentioned in Appendix D.3, the output size of the linear models is bounded by O(n 3 ).
The issue of finding a safe and complete genome assembly algorithm (for a natural problem formulation, namely that of a closed arc-covering walk) has been open for two decades, and recently solved in [59] . On genome assembly graphs constructed from perfect data, omnitigs led to significantly bipartite graph longer strings than those of unitigs, proving the potential usefulness of a rigorous mathematical approach to genome assembly. However, because of many practical aspects of the read data (linear chromosomes, missing coverage, errors and diploidy) it remained open whether this theoretical breakthrough can also be made practical. A further issue with the existing results [59, 10, 1] is their very problem-specific techniques, which seem extremely difficult to generalize. In this paper we presented an entirely new perspective to characterize safe solutions for such covering problems, with a unified methodology, having many implications. First, the hydrostructure of a walk highlights important reachability properties of a graph from the perspective of the safe walk. This results in simpler and complete characterisations (in the form of a YES-certificate) of the previously studied types of covering walks. Second, these characterisations are directly adaptable to optimal verification algorithms (except for k-st safe with k = 1, ∞ in non-strongly connected graphs), and simple enumeration algorithms. We also improved our k-circular safe and k-st safe (for k = 1, ∞) algorithms to optimality using the optimal 1-circular safe algorithm [9] and the incremental computation of the hydrostructure, respectively. Third, the flexibility of the hydrostructure allowed us to easily handle further practical aspects. Namely, we easily extended the characterizations for the subset covering model, for all k-circular safe and k-st safe problems. Moveover, we easily generalized the hydrostructure for the subset visibility model, so that the existing characterizations can be applied directly without changes. Lastly, even though the hydrostructure is developed mainly for arc-covering walks motivated by genome assembly, it reveals a novel fundamental insight into the structure of a graph, which can be of independent interest.
We deem that the extensive array of covering problems considered this paper, together with the simple characterizations and enumeration algorithms, proves that the hydrostructure is an ideal toolkit for obtaining safe, complete and practical genome assembly algorithms. As such, it could lead to another theoretical breakthrough with significant practical improvements, in the same way as the FM-index [18] is now at the core of start-of-the-art read mapping tools.
[2] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false 
Lemma A.1. Let W be a trivial a-b walk in a strongly connected graph with n nodes and m arcs and let e ∈ Heart(W ) be an arc with e / ∈ {a, b}. After O(m) time preprocessing, the query "is there an a-b path in G \ e" can be answered in O(1)-time.
Proof. The query in Theorem 2.1 (c) (for x = head(a) and y = tail(b)) is equivalent to answering whether there exists an a-b path in G \ e, because we can prove that there is always a b-a path that does not contain e if W is trivial. A b-a path exists since G is strongly connected. And this path does not contain e, as W is trivial so every path through e ∈ Heart(W ) contains the whole W starting from a. Proof. We decompose W into aZb, where a and b are arcs. We first prove that if Vapor(aZb) is not exactly the open path Z, then Vapor(aZb) = G and aZb is avertible. Assume that Z is not an open path, or Vapor(aZb) contains a node or arc x / ∈ Z. We distinguish three cases: • If Z is not an open path, then it contains a cycle which can be removed to create a walk from a to b not containing aZb.
• If x = a (or x = b) then by definition R − (aZb) (or R + (aZb)) contains a walk from a to b that does not contain aZb.
• If x / ∈ {a, b}, then by definition of R + (aZb) and R − (aZb), there are paths from a to x and from x to b that do not contain aZb. And since x is not in aZb, these paths can be joined together to create a walk from a to b that does not contain aZb. In each case, there is a walk from a to b that does not contain aZb. And since b is the last element of this walk, by strong connectivity this walk can be extended within G to reach any node or arc in G\Z without containing aZb. By definition, the walk Z is in Vapor(aZb) as well. So R + (aZb) = G, and by symmetry one can prove that R − (aZb) = G, so Vapor(aZb) = G. This also makes aZb avertible, since, for any pair x, y ∈ G, every occurrence of aZb in an x-y walk can be replaced with an a-b walk that does not contain aZb.
We now prove that if Vapor(aZb) is an open path equal to Z, then aZb is bridge-like. Since Z is an open path, b / ∈ Z else it would repeat the node tail(b). However, b ∈ R − (aZb) by definition, so we have b / ∈ R + (aZb), which means aZb is bridge-like because of the pair (a, b).
Lemma 3.4. The hydrostructure on a bridge-like path aZb exhibits the following properties: a. (Safety) Every walk from x ∈ Sea(aZb) to y ∈ Cloud(aZb) contains aZb as a subwalk. b. (Avoidance) Every x ∈ Cloud(aZb) and y ∈ Sea(aZb) have an x-y walk with no subwalk aZb. c. (Separation) a ∈ Sea(aZb) and b ∈ Cloud(aZb). • (Cloud, Sea), where aZb is univocal or R-univocal.
Proof. We prove the statements in reverse order for simplicity.
(e) We first prove all the incident pairs involving the River(aZb), and then the residual pairs involving the Vapor(aZb), and finally between Sea(aZb) and Cloud(aZb).
-We show that x, y ∈ (River, Vapor) and x, y ∈ (River, Cloud) do not exist. Since x ∈ River(aZb), it holds that x / ∈ R + (aZb) and therefore x = a. Thus, y ∈ R − (aZb) (and hence Vapor(aZb) or Cloud(aZb)), implies x ∈ R − (aZb) because of (x, y), as prepending x ( = a) does not make aZb a subwalk. This contradicts that x ∈ River(aZb) by definition. By symmetry x, y ∈ (Vapor, River) and x, y ∈ (Sea, River) do not exist as well.
-For x, y ∈ (Vapor, Cloud) we necessarily have y = b, because x ∈ R + (aZb) would otherwise add y ∈ R + (aZb), removing it from Cloud(aZb). When y = b we get aZb as a subwalk, preventing R + (aZb) from covering y. By symmetry, x, y ∈ (Sea, Vapor) implies x = a.
-We show that x, y ∈ (Sea, Cloud) implies x = a and y = b, which contradicts our definition of aZb as being from arc to arc. This is because x ∈ R + (aZb) would add y ∈ R + (aZb) if y = b, as described above, and symmetrically y ∈ R − (aZb) implies x = a. Let x, y ∈ (Cloud, Sea). We prove that if x is an arc then aZb is R-univocal (by symmetry if y is an arc then aZb is univocal), and hence trivial. Then x ∈ R − (aZb) but y / ∈ R − (aZb), so x = b because each other arc is covered by R − (aZb) using its head. Assume for a contradiction that aZb contains a join node. Then by strong connectivity an arc e entering aZb at this join node needs to be (forwards) reachable from y = head(b), let W be such a walk of minimum length. But then, since y / ∈ R − (aZb), W (being a b-e walk) needs to have aZb as subwalk, which contradicts that it is minimal.
Where it applies, the necessity of the connections follows from strong connectivity of the graph since no other connections exist, as proved above.
(d) Let W P be the prefix of aZb ending in its last split node. We show that if Sea(aZb) = {a}, then for every node and arc x ∈ Sea(aZb) with x = a there is a path P in Sea(aZb) containing x which starts from an arc e with tail(e) ∈ Vapor(aZb) and ends in a. Notice that tail(e) is a split-node, since P diverges from aZb at e, ensuring that tail(e) is in W P . This will prove the first part of the statement because it allows to form a cycle through a and x = a within W P ∪ Sea(aZb), because the path would leave aZb latest at its last split node to enter Sea(aZb) (using Lemma 3.4 (e)). And this will also prove the second part by symmetry.
For a node or an arc x = a in Sea(aZb), by definition there is an a-x walk inside R + (aZb) that does not have aZb as subwalk. Starting from head(a) ∈ Vapor(aZb) this walk exits Vapor(aZb) into the Sea(aZb) (since R + (aZb) = Vapor(aZb) ∪ Sea(aZb)), with an arc e having tail(e) ∈ Vapor(aZb). By strong connectivity, there is also a path from x to a. Notice that both the paths from e to x and from x to a are completely within the Sea(aZb) because the only arc leaving Sea(aZb) is a, by Lemma 3.4 (e).
This also proves that there exists such a circular path for a if there exists some x ∈ Sea(aZb) = a. For Sea(aZb) = a, we have no split nodes on aZb because R + (aZb) does not leave aZb. This makes W P = ∅ resulting in no SCC.
(c) By definition, a ∈ R + (aZb) and a / ∈ R − (aZb) when aZb is bridge-like, resulting in a ∈ Sea(aZb). Symmetrically, we prove b ∈ Cloud(aZb).
(b) By strong connectivity, there always exists an x-y path. If such a path contains aZb, then consider its prefix, say P , that ends at the first occurrence of a. Notice that if Sea(aZb) = {a}, then y = a, making P a path from x to y without having aZb as subwalk. Otherwise, by Lemma 3.4 (d), there is a path from a to every such y ∈ Sea(aZb) which does not contain b, which when appended to P gives us the desired walk with no subwalk aZb.
(a) The only way to reach Sea(aZb) from Cloud(aZb) is through Vapor(aZb) (by Lemma 3.4 (e)) so every path from Sea(aZb) to Cloud(aZb) passes through Vapor(aZb). Further, Vapor(aZb) can only be entered from Sea(aZb) through a (by Lemma 3.4 (e)) and can only be exited to Cloud(aZb) through b (by Lemma 3.4 (e)), and every such path contains the entire aZb as subwalk (by Lemma 3.3).
Theorem 3.6. Let W = W l ZW r be a trivial walk where Heart(W ) = Z. (b) Let W = W j ZW s be a subwalk of W , with W j , W s not empty. Then start(W j ) is a split node. Let e be one of its outgoing arcs e that is not in Z. By strong connectivity, there is an e-start(W ) path, which would repeat start(W ) if it would have Z as subwalk, and therefore does not have Z as subwalk. Prepending this path with W j creates a start(W )-start(W ) path that does not have Z as subwalk. Symmetrically, there is a end(W )-end(W ) path without Z as subwalk. Additionally, since W is avertible, there is a start(W )-end(W ) walk that does not have Z as subwalk. Since neither of these three walks starts or ends with a node or arc in Z, they can be joined into a single start(W )-end(W ) walk that does not have Z as subwalk, which by Lemma 3.3 proves that W is avertible.
Lemma 6.1. Given a bridge-like walk aZb it holds that R + (aZb) = aZ ∪ arc e∈Zb R + sib (e). Proof. (⊆) Let x ∈ R + (aZb). If x ∈ aZ, then it trivially holds, so consider x / ∈ aZ. Then, since aZb is bridge-like, x ∈ Sea(aZb). So by Lemma 3.4 (d), there is an a-x path P in Sea(aZb)∪Vapor(aZb).
Let v be the last element of P in Vapor(aZb); it exists since head(a) ∈ Vapor(aZb), and since Vapor(aZb) is a path by Lemma 3.3, v is a node.Let e be the outgoing arc of v in P and e its sibling in Zb; notice that e = b, since b ∈ Cloud(aZb). By definition of R + sib (·), it holds that the suffix of P starting from e is in R + sib (e) and, as such, x ∈ R + sib (e). (⊇) By definition, aZ ⊆ R + (aZb). Let x ∈ R + sib (e), for some arc e from Zb. Since aZb is bridgelike, by Lemma 3.3, Z is an open path, and therefore aZ is a path. As a result, there is a path P from a to tail(e) via a prefix of Z that does not contain e. Since x ∈ R + sib (e), P can be extended to x without using e. So there is a walk from a to x without using e ∈ Zb, so x ∈ R + (aZb).
Lemma 6.2. Let aZb be a bridge-like walk where b is a split-arc and e a split-arc after a. Then (a) R + sib (e) ⊆ R + sib (b) and
(a) Let x ∈ R + sib (e). Then by Lemma 6.1, x ∈ R + (aZb), so there is a walk from a to x which, by Lemma 3.4 (c), does not include b. Moreover, by Lemma 3.4 (d), there is a walk from each split-sibling of b to a that does not include b.
Moreover, since by Lemma 3.3 it holds that Z is an open path, it follows that aZ does not contain b. Therefore, we can prepend a suffix of aZ to W (without repeating the last node of Z), resulting in an e-x walk W in G \ {b}. Since x / ∈ R + sib (e) and W starts in e, W must contain a suffix starting in some occurrence of e that contains no elements of R + sib (e). But then that suffix of W is an e-x walk in G \ (R + sib (e) ∪ {b}), a contradiction. (⊇) If x ∈ R + sib (e) then x ∈ R + sib (b) by Lemma 6.2 (a). Otherwise there is an e-x walk in G\(R + sib (e)∪{b})}. Since aZb is bridge-like, it holds that each split sibling of b is in Sea(aZb). By Lemma 3.4 (d) there is a walk from each split sibling of b to e in Sea(aZb)∪Z. Notice that by Lemma 3.4 (c), b ∈ Cloud(aZb), so these walks do not contain b since Z is Vapor(aZb). So there exists an tail(b)-x walk via e in G \ {b}, so x ∈ R + sib (b). Theorem A.2. A strongly connected graph G with n nodes and m arcs has at most m maximal 1-circular safe walks, of which at most O(n) are bridge-like trivial and at most O(n) are non-trivial.
Proof. Let W be a trivial bridge-like walk. Then there is a pair of elements x, y ∈ G such that each x-y walk has W as subwalk. Since W is trivial this is equivalent to each x-y walk containing some edge e ∈ Heart(W ). Therefore the removal of e would disconnect y from x, which, since G is strongly connected, proves that e is a strong bridge. Moreover, by [27] , there are at most O(n) strong bridges, so there are at most O(n) maximal bridge-like trivial walks. The bound on non-trivial 1-circular safe walks follows from Theorem 2.1 (b).
As described in Section 4, since trivial walks are naturally safe the characterisations are stated only for non-trivial walks. 1-Circular) . A non-trivial walk W is 1-circular safe iff Vapor(Heart(W )) is a path.
Proof. (⇒) Let Vapor(Heart(W )) not be a path. Let aZb := Heart(W ), a be a sibling join arc of a and b be a sibling split arc of b. Then, by Lemma 3.3, aZb is avertible. We prove that aZb is not 1-circular safe by constructing a circular arc-covering walk C that does not contain aZb. Let P be a a -b walk, such that aZb is not a subwalk of P , which exists since aZb is avertible. Let C be an arbitrary circular arc-covering walk of G. If C does not contain aZb the claim holds, otherwise consider C obtained from C , by replacing every aZb subwalk with aZP Zb. Concluding, since aZb is not 1-circular safe, it holds that W is not 1-circular safe.
(⇐) Let Vapor(Heart(W )) be a path. Then Vapor(Heart(W )) is not the whole G. Moreover, by Lemma 3.3, Heart(W ) is bridge-like, so there are x, y ∈ G such that each x-y walk has Heart(W ) as a subwalk. Therefore, since every circular arc-covering walk C in G contains both x and y and hence a subwalk from x to y, Heart(W ) is a subwalk of C (and hence 1-circular safe). Further, since C is circular, the whole W is 1-circular safe, as Heart(W ) can only be traversed by also passing through its univocal extension.
Theorem 4.2 (k-Circular). A non-trivial walk W is k-circular safe for k ≥ 2, iff Vapor(Heart(W )) is a path and River(Heart(W )) is non-empty.
Proof. (⇒) We first prove that W is not k-circular safe if Vapor(Heart(W )) is not a path or River(Heart(W )) is empty.
• If Vapor(Heart(W )) is not a path, then using Theorem 4.1 W is not 1-circular safe, or there is a circular arc-covering walk C not containing W . Thus, a collection of k copies of C is also arc-covering not containing W , proving that W is not k-circular safe.
• If Vapor(Heart(W )) is a path, and River(Heart(W )) is empty, we can prove that W is not k-circular safe for k ≥ 2 because for a non-trivial W it holds that Cloud(Heart(W )) ∪ Vapor(Heart(W )) and Sea(Heart(W )) ∪ Vapor(Heart(W )) are each strongly connected. Thus, two different walks can separately cover them as River(Heart(W )) is empty.
We only prove that Cloud(Heart(W )) ∪ Vapor(Heart(W )) is strongly connected as the other follows by symmetry. Since W is non-trivial, Heart(W ) starts with a join arc a and ends with a split arc b. If Cloud(Heart(W )) = {b} then clearly it is the join sibling of a, making Cloud(Heart(W )) ∪ Vapor(Heart(W )) a cycle and hence strongly connected. Otherwise, if Cloud(Heart(W )) = {b} then the strong connectivity follows by Lemma 3.4 (d).
(⇐) If Vapor(Heart(W )) is a path then Heart(W ) is bridge-like by Lemma 3.3. If River(Heart(W )) is not empty, since the graph is strongly connected we can enter River(Heart(W )) only from Cloud(Heart(W )) (by Lemma 3.4 (e)) using some arc. Hence, every walk covering this arc requires a subwalk from River(Heart(W )) to Cloud(Heart(W )), which passes through Sea(Heart(W )) (by Lemma 3.4 (e)). Using Lemma 3.4 (a) we get that this subwalk necessarily contains the walk W making it k-circular safe.
We also use the following property for our efficient algorithm to compute k-circular safe walks. Proof. By symmetry of the statement, we only prove that if W is a 1-circular safe walk of G that is not k-circular safe then XaZ is a k-circular safe walk of G. This also implies that Q is non-trivial otherwise it is implicitly k-circular safe. Further, being a subwalk of the 1-circular safe W makes Q := XaZ also 1-circular safe. Let Heart(Q) = aZ * b * , which is either aZ or a prefix of aZ. Since aZb is a non-trivial heart, there exists a sibling split arc b of b. We claim that for any such sibling b , we have b ∈ River(aZ * b * ), which is equivalent to b / ∈ R + (aZ * b * ) ∪ R − (aZ * b * ). Now, aZ is bridge-like (since aZb is bridge-like), so each start(aZ)-end(aZ) walk has aZ as subwalk. Since end(aZ) = tail(b ) it follows that each a-b walk has aZ as subwalk, and hence its prefix aZ * b * . Thus, b / ∈ R + (aZ * b * ). Further, we know that b ∈ Sea(aZb) as it is surely in R + (aZb) (by definition) and not in Vapor(aZb) (for bridge-like aZb by Lemma 3.3). So any path from b to b * ∈ Vapor(aZb) surely enters Vapor(aZb) through a (by Lemma 3.4 (e)). Hence it has aZ * b * as a subwalk since Vapor(aZb) is a path and aZ * b * is a prefix of aZb. Thus, b / ∈ R − (aZ * b * ). Thus b / ∈ (R + (aZ * b * ) ∪ R + (aZ * b * )) implying that b ∈ River(aZ * b * ), and by Theorem 4.2 that aZ * b * is k-circular safe. Therefore, since Heart(XaZ) = aZ * b * , we conclude that XaZ is k-circular safe. By symmetry ZbY is also k-circular safe.
Our characterisation employs the notion of s-t suffix-prefix covered for the safety of trivial walks. It describes whether an arc of a walk is in its suffix starting at s or in its prefix ending at t. This notion thus identifies arcs that cannot be covered without covering the whole walk, rendering it safe. We formally define it using proper s-suffix and t-prefix as follows.
Definition C.1 (Proper s/t-Suffix/Prefix). For a walk aZb, the proper s-suffix (or t-prefix) is its maximal suffix starting in s (or prefix ending in t) or the empty sequence if s / ∈ Z (or t / ∈ Z). Recall that Z starts and ends with a node.
Definition C.2 (s-t Suffix-Prefix Covering). An arc e ∈ aZb is s-t suffix-prefix covered in aZb if e belongs to the s-suffix or to the t-prefix of aZb.
Furthermore, we use the following property of the trivial avertible walks in our main proof. Lemma C.3. For a trivial avertible walk aZb in a strongly connected graph G, the graph G \ Heart(aZb) is also strongly connected.
Proof. Observe that since Heart(aZb) is from arc to arc and Heart(aZb) is a biunivocal path, removing Heart(aZb) from G does not remove any endpoint of remaining arcs. For any two nodes x, y in G \ Heart(aZb), since aZb is avertible there is an x-y (or y-x) walk that does not have aZb as a subwalk. Thus, the graph G \ Heart(aZb) is strongly connected.
We now prove our characterisation of k-st safe walks, by first giving a characterisation that works for trivial walks and non-trivial hearts. For simplicity of presentation, we will separately characterize the safety of the wings of non-trivial walks.
Theorem 5.1 (k-st Safe Trivial Walks and Non-Trivial Hearts). A trivial walk W (or a non-trivial heart W ) is k-st safe iff it is a single arc or (a) River(W ) cannot be covered with k walks, or (b) s / ∈ R − (W ), or (c) t / ∈ R + (W ), or (d) W is trivial and some arc e in Heart(W ) is not s-t suffix-prefix covered in W .
Proof. If W is a single arc, it is trivially safe. Otherwise, let W = aZb where a and b are arcs. (⇒) When the conditions (a) to (d) are false, we show that aZb is not safe as follows. Note that if (d) is false, then at least one of s and t are in aZb. We distinguish the cases where the walk is avertible or bridge-like.
When aZb is avertible, if it is trivial, then by Lemma C.3 there exists an arc-covering circular walk W in G \ Heart(aZb) because it is a strongly connected component. This circular walk can be extended to get a linear s-t walk starting from a suffix of aZb and (or) ending at a prefix of aZb. Since all arcs in Heart(aZb) are s-t suffix-prefix covered in aZb, this walk covers all the arcs of Heart(aZb) without having aZb as a subwalk. Thus, aZb is not k-st safe. On the other hand, if aZb is an non-trivial heart, then aZb is not 1-circular safe by Theorem 4.1. Hence, there exists a circular arc-covering walk in G that does not have aZb as subwalk. Such a walk can be repeated such that it starts in s and ends in t, forming an arc-covering s-t walk that does not have aZb as subwalk. Thus, aZb is not k-st safe.
For bridge-like aZb we describe a set of k s-t walks that together cover G, where none has aZb as subwalk. Since s ∈ R − (aZb) and t ∈ R + (aZb), an s-t walk can cover the cloud-related SCC and the sea-related SCC (Lemma 3.4 (d)), necessarily covering Cloud(aZb) and Sea(aZb). For a non-trivial heart it then also covers Vapor(aZb). For trivial walks, all arcs in Heart(aZb) can be covered by the proper s-suffix and (or) t-prefix of aZb, since they are s-t suffix-prefix covered in aZb. Finally, River(aZb) can be completely covered by the k walks between Cloud(aZb) and Sea(aZb), because (a) is false. Hence, G can be covered without going from Sea(aZb) to Cloud(aZb) and, therefore, without having aZb as a subwalk. Thus, aZb is not k-st safe. (⇐) If River(aZb) cannot be covered with k walks, then to cover River(aZb) at least one walk needs to enter River(aZb) twice. This ensures that it has a subwalk from Sea(aZb) to Cloud(aZb) and hence aZb (by Lemma 3.4 (a) ). If s / ∈ R − (aZb), then the only way to cover b (and Cloud(aZb)) is through a walk from Sea(aZb) to Cloud(aZb), necessarily having aZb as subwalk (by Lemma 3.4 (a) ). This can be symmetrically proven for t / ∈ R + (aZb). Finally, if aZb is a trivial walk with an arc in Heart(aZb) that is not s-t suffix-prefix covered in aZb, then it can only be covered by using aZb as a whole.
Lemma C.4. A non-trivial 1-circular safe walk W l W W r with W = Heart(W l W W r ) has W l in R + (W ) and W r in R − (W ).
Proof. Since W l W W r is non-trivial, W is non-trivial and therefore Sea(W ) = {start(W )} from which by Lemma 3.4 (d) follows that Sea(W ) with some part of Vapor(W ) forms an SCC. But then, every R-univocal walk ending in start(W ) is in Sea(W ) ∪ Vapor(W ) = R + (W ) and W l is a subwalk of at least one of these walks. By symmetry, W r is in R − (W ).
Theorem 5.2 (Wings of Non-Trivial k-st Safe Hearts). A non-trivial 1-circular safe walk W l W W r , where W is its heart, W l its left and W r its right wing, is k-st safe iff W is k-st safe and (a) River(W ) cannot be covered with k walks, or (b) either both of s ∈ W l and t ∈ W r are false, or exactly one is true with:
• if s ∈ W l , then t / ∈ R + (W ) ∪ W r and s / ∈ W , and • if t ∈ W r , then s / ∈ R − (W ) ∪ W l and t / ∈ W .
Proof. If the River(W ) has cannot be covered with k walks, then to cover it using only k solution walks at least one walk enters River(W ) twice. By Lemma 3.4 (a) and (e) this walk makes W l W W r safe as its subwalk necessarily goes from Sea(W ) to Cloud(W ) which completely contain the wings (by Lemma C.4). Now, the wings are also safe if s / ∈ W l and t / ∈ W r , as they are univocal extensions. They can also be safe with s ∈ W l , if we are required to separately cover the prefix of the left wing before s, and the location of t does not allow the walk to end prematurely before covering the entire W l W W r . Note that if s ∈ W l ∩ W such a prefix would be covered starting from s itself, negating the above requirement making the wings not safe. Further, covering the entire W l W W r requires such a walk to have a subwalk from Sea(W ) to Cloud(W ) without ending before completing the right wing. This can be ensured by t / ∈ R + (W ) ∪ W r , else it can also end in Vapor(W ), Sea(W ) (as W is non-trivial) or before completely covering W r . By symmetry we have the corresponding criteria for t ∈ W r .
In contrast to the circular models, linear models do not require the graph to be strongly connected to admit a solution. Our hydrostructure (and hence the characterisations described earlier) handle only strongly connected graphs, but we can extend them to a graph G which is not strongly connected but admits a solution. Consider the SCCs of G and observe that single nodes can also be SCCs. We refer to an arc as inter-SCC if its endpoints belong to different SCCs of G, otherwise we refer to it as intra-SCC arc. Trivially, in the 1-linear model, the graphs have the following structure as a single s-t walk must cover the whole graph:
Lemma C.5. Let G = (V, E) be a graph, and let s, t ∈ V . It holds that G admits an s-t arccovering walk if and only if the DAG of SCCs of G is a path, such that between any two SCCs consecutive in this path there is exactly one inter-SCC arc, s is in the (only) source SCC and t in the (only) sink SCC.
By processing the SCCs and the inter-SCC arcs of non-strongly connected graphs separately, we can reduce the characterisations and algorithms for the 1-linear model in non-strongly connected graphs to the 1-linear model in strongly connected graphs. For that we define the entry points of an SCC as s or nodes that have an incoming intra-SCC arc, and the exit points of an SCC as t or nodes that have an outgoing intra-SCC arc. Note that each SCC of a graph that admits a solution to the 1-linear model has exactly one entry point and exactly one exit point, by Lemma C.5. This allows us to decompose the graph into a sequence D := (S 1 , e 1 , S 2 , . . . , e −1 , S ) where each S i is an SCC and each arc e i is an inter-SCC arc. We call this the sequence decomposition of the graph. Observe that each S i is of one of the following three forms: it can be a single node, a cycle of at least one arc, or a nonempty graph that is not a cycle. Single nodes are a special case, as they allow to join their predecessor and successor arcs into a single safe walk. Cycles are a special case as well, as our characterisations on strongly connected graphs are defined only for non-cycles, so we need to handle these separately as well.Finally, for a nonempty SCC S i that is not a cycle, it holds that the 1-st safe walks for G, that are completely contained in S i , are also safe for single s -t arc-covering walks in S i , where s and t are the entry and exit points of S i , respectively. The sequence structure allows us to decompose solution walks into their subwalks through each of the elements in the sequence. Note that the sequence structure also implies an order in which the arcs in the graph need to be covered. This allows us to generalise the univocal extension for inter-SCC arcs to completely describe safe walks that contain inter-SCC arcs. Additionally, these also have all safe walks in circular SCCs as subwalks (as proven in Theorem C.6 below), solving this special case.
We define the inter-SCC univocal extension U (e) of an inter-SCC arc e as a walk XY Z where Y is from arc to arc and X and Z are within single SCCs and three further conditions hold. First, Y contains e and contains only inter-SCC arcs and single-node SCCs. Second, X is the longest walk ending in start(Y ) that is R-univocal in the SCC of tail(start(Y )) (ignoring inter-SCC arcs) and that visits the entry point of its SCC at most twice, and if it visits it twice then the first occurrence is start(X). And third, Z is the longest walk starting in end(Y ) that is univocal in the SCC of head(end(Y )) (ignoring inter-SCC arcs) and that visits the exit point of its SCC at most twice, and if it visits it twice then the second occurrence is end(Z). We get the following characterisation:
Theorem C.6 (1-st Safe Walks in General Graphs). In a non-strongly connected graph G that admits a solution to the single linear model for given s and t, a walk is 1-st safe iff:
(a) it is a subwalk of the inter-SCC univocal extension of an inter-SCC arc, or (b) it is 1-s't' safe in an SSC S of G, where s is the entry point of S, and t is the exit point of S.
Proof. We start by handling case (b). If W is 1-st safe in an SCC of G that is not a cycle where s is the entry point of S and t is the exit point of S, then W is part of each solution walk in G and therefore safe. On the other hand, if W is not 1-st safe in its SCC, then it can be avoided by a solution walk in G, and is therefore unsafe. This proves the theorem for walks that are in an SCC that is not a cycle, so we exclude those walks for the rest of the proof.
To prove that W is safe if it is a subwalk of the inter-SCC univocal extension U (e) = XY Z of an inter-SCC arc e, we prove that XY Z is safe. By definition Y is biunivocal and therefore safe. We prove the claim that after traversing Y each solution walk needs to traverse Z, from which the safety of XY Z follows by symmetry. By definition, Z is in a single SCC S and start(Z) is its unique entry point. If Z does not contain the exit point of S, then the claim holds. On the other hand, if Z does contain the exit point of S, then it can ignore it the first time: by the strong connectivity of S the exit point has an outgoing arc within S, and this arc cannot be covered before reaching the exit point for the first time, but it must be covered before exiting S. If Z contains the exit point a second time, then by definition Z ends there, so the exit point cannot end Z early. Thus, after traversing XY Z each solution walk needs to traverse Z, which proves the safety of Y Z, and by symmetry the safety of the entire XY Z.
Now it remains to prove that there are no other safe walks. We first consider walks that contain an inter-SCC arc, and then all remaining walks.
If W contains an inter-SCC arc e, but is not a subwalk of its inter-SCC univocal extension O(e) = XY Z, then without loss of generality we can assume that a proper prefix of W has end(Y )Z as subwalk (the case where a proper suffix of W has Xstart(Y ) as subwalk is symmetric). Let S be the SCC of Z. Then W is unsafe if Z ends in a node v that has at least two outgoing arcs in S: since S is strongly connected, when a solution walk first reaches v it can continue with either of the outgoing arcs in S and then cover the rest of S. On the other hand, if Z ends in the exit point of S that is not a split node in S, then, by definition, Z contains it twice. But then, all nodes in S have exactly one outgoing intra-SCC arc, and therefore it is a cycle. So between the two occurrences of the exit point in Z, S is completely covered, proving that there is a solution walk that exits S after traversing end(Y )Z, in addition to a solution walk that traverses S one more time after traversing end(Y )Z. Therefore, W is not safe.
If W contains no inter-SCC arc, is not a subwalk of any inter-SCC univocal extension and is not fully contained in an SCC different from a cycle, then it is contained in a single SCC S that is a cycle. Let U (e) = XY Z be the inter-SCC univocal extension of the inter-SCC arc e that enters S. By definition, Z is inside S, and since W is not a subwalk of this inter-SCC univocal extension, it is not a subwalk of Z. But Z is the maximal safe subwalk in S, since there is a solution walk that traverses end(Y )Z and then exits S, as proven above. Therefore, W is not safe.
In the ∞-linear model, there exists a simple reduction from non-strongly connected graphs to strongly connected graphs.
Theorem C.7 (∞-st Safe Walks in General Graphs). A walk is ∞-st safe in a non-strongly connected graph G that admits a solution to the infinite linear model for given nodes s and t iff the walk is ∞-st safe in G ∪ {(t, s)}, which is strongly connected.
Proof. Since G can be covered by a set of s-t walks, it holds that G ∪ {(t, s)} is strongly connected. For each set of solution walks in G, a set of solution walks in G ∪ {(t, s)} can be constructed by repeating one of the walks through (t, s). Similarly, for each set of solution walks in G ∪ {(t, s)}, a set of solution walks in G can be constructed by splitting all walks that contain (t, s). Therefore, a walk in G is ∞-st safe in G if and only if it is ∞-st safe in G ∪ {(t, s)}.
Using Theorem C.6, the 1-st safe algorithm for strongly connected graphs (see Theorem 6.3) can be extended trivially to get an algorithm with the same time bounds for non-strongly connected graphs. The algorithm solves all the 1-st safe subproblems in SCCs and adds the inter-SCC univocal extensions to the solution. Since each SCC intersects with at most two inter-SCC univocal extensions of which one starts at its entry point and one ends at its exit point, the safe walks within each SCC can be checked for being subwalks of the inter-SCC univocal extensions by trivial alignment. The total length of the inter-SCC univocal extensions that intersect with that SCC (limited to the part within the SCC) is O(n i ) since the SCC is not a cycle and the intersecting parts are univocal or R-univocal. By the same argument, the intersecting parts contain each arc at most once. Therefore, the unique starting point of an alignment can be found in constant time after O(n i ) time preprocessing (by building an array that maps from arc ids in the SCC to their positions in the intersecting parts of the inter-SCC univocal extensions). Afterwards the alignment is Remark C.9. For k s-t arc-covering walks where 1 < k < ∞, our characterization and algorithms do not simply extend to non-strongly connected graphs. Note that a reduction similar to 1-st safe does not suffice as the graph can be any DAG of SCCs, which is not necessarily a path.
Hence the SCCs may have up to k different entry and k different exit points. This is essentially an entirely different model for linear-safe walks from multiple sources and multiple sinks, which would require further case analysis and generalisations to our current characterisations of linear models. This becomes particularly complex because of the possible existence of such sources or sinks in different components of the hydrostructure, or wings of the walk. Even though we deem this to be feasible, it may require an entirely new approach and thus it is beyond the scope of this work. Proof. Each node and arc can be annotated with its membership in R + (W ) and R − (W ) using Algorithm 1 and its symmetric variant in O(m) time. It remains to prove the correctness of Algorithm 1.
• Suppose Algorithm 1 reaches Line 5 and returns G. If W is not an open path, then by Lemma 3.3 this is correct. Otherwise, if W is an open path, there is an arc e ∈ R such that tail(e) / ∈ W ∧ head(e) ∈ W ∧ e = start(W ). Then, there is a walk from start(W ) via e to end(W ) that does not contain W as subwalk, so W is avertible, and by Lemma 3.3 it follows that outputting G is correct, because G = Vapor(W ) ⊆ R + (W ) ⊆ G.
• Suppose Algorithm 1 reaches Line 4 and returns R . Then for that to be correct, by Lemma 3.3 W must be bridge-like and R must be equal to R + (W ).
Assume for a contradiction that W is avertible. Then by Lemma 3.3 it holds that Vapor(W ) = G, and therefore R + (W ) = G. Hence, by definition of R + (·), there is a start(W )-end(W ) walk W that does not have W as subwalk. Such a walk leaves W before reaching end(W ) to avoid having W as subwalk. But then it must enter W again at an arc e other than start(W ) before it reaches end(W ) for the first time. Therefore, e ∈ R and it holds that e / ∈ W and head(e) ∈ W . But then the condition in Line 3 would be false and Algorithm 1 would not reach Line 4, a contradiction.
Therefore, W is bridge-like, and it remains to prove that R = R + (W ). (⊆) Let x ∈ R . Then there is a start(W )-x walk in G \ end(W ), so x ∈ R + (W ). (⊇) Let x ∈ R + (W ). Then there is a start(W )-x walk in G that does not contain W as subwalk. This walk cannot contain end(W ), since otherwise one of its prefixes until end(W ) would prove end(W ) ∈ R + (W ), contradicting Lemma 3.4 (c). So x ∈ R .
The characterisation can be directly adapted to get a verification algorithm for evaluating whether a given walk is safe in 1-circular and k-circular models. A trivial walk W is easily identified in O(|W |) time by checking for univocal walks. For a non-trivial walk W the hydrostructure can be computed in linear time (Theorem 3.5) and the characterisation can be verified in O(|W |) time resulting in an O(m) time verification algorithm for both 1-circular safe and k-circular safe walks.
Since every trivial walk is 1-circular safe and k-circular safe, they can be enumerated by computing univocal extensions of each arc in O(mn) time. For reporting all non-trivial maximal 1-circular safe and k-circular safe walks, we use the two pointer algorithm on a candidate solution. A candidate solution can be computed by arranging the m arcs in some circular order, and adding the shortest path between adjacent arcs to complete the closed arc-covering walk of size O(mn). To get an arc-covering solution made up of k closed walks, we can have k identical copies of this O(mn)-size walk. Now, using the two-pointer algorithm (Theorem 2.1 (a)) on one of these identical walks, with the above linear time verification algorithm we can enumerate all non-trivial maximal 1-circular safe and k-circular safe walks in O(m 2 n) time.
Alternatively, non-trivial k-circular safe walks can computed using non-trivial 1-circular safe walks in O(mn) time. This is because the amount of non-trivial 1-circular safe walks is O(n) (Theorem 2.1 (b) ). Computing their hydrostructure in O(m) time either verifies them to be kcircular safe or its two subwalks as k-circular safe (using Lemma 4.3). Hence, using the O(mn) time optimal 1-circular safe algorithm [9] we get the following result.
Theorem D.1. Given a strongly connected graph with m arcs and n nodes, all the maximal kcircular safe walks can be reported in O(mn) time.
Note that the k-st safe problems are equivalent for all k ≥ m. The characterisation can be directly adapted to get a verification algorithm for evaluating whether a given walk is k-st safe. A trivial walk W is easily identified in O(|W |) time by checking for univocal walks. The hydrostructure can be computed in linear time (Theorem 3.5) and thereafter the s and t membership queries are answered in constant time. The s-t suffix-prefix criteria can be verified in O(|W |) time. Thus, the verification algorithm for k-st safety requires O(m + f (m, n)) time, where time required to compute the minimum walk-cover is f (m, n).
For enumerating all the maximal k-st safe walks we require the set of all 1-circular safe walks, which are computable in O(mn) time [9]. We compute the hydrostructure for each non-trivial Heart(W ) as well as each trivial W , and check the conditions from Theorems 5.1 and 5.2. If a walk is k-st safe, we report it. Otherwise, we use the two-pointer algorithm to report its maximal safe substrings as in Theorem 2.1 (a). 
We prove that we can enumerate the maximal safe subwalks of maximal trivial avertible 1-circular safe walks in the linear models in O(mn) time plus O(n) executions of the two-pointer algorithm using the incremental hydrostructure, which matches the time bounds for computing k-st safe from non-trivial 1-circular safe walks for the respective model. We first restrict our description to Ecovering linear models. Consider that for a trivial avertible walk W l W W r where W l is its left wing, W r is its right wing and W is its heart by Theorem 3.6 (b) only subwalks of W l W or W W r can be bridge-like. Therefore, the k-st safety of other subwalks of W l W W r can be decided without the hydrostructure by checking the location of s and t within the subwalk. This can be done for all such subwalks in amortised O(|W l W W r |) time using the two-pointer algorithm, so in total O(mn) time for all walks.
For those subwalks that are subwalks of W l W or W W r , we describe only W l W since the argument for W W r is symmetric. Consider that W l W is trivial, so by the conditions on the heart in the linear models (see Theorem 5.1 (d)), it may have non-k-st safe subwalks only if W l W contains s. It does not matter if it contains t, since any subwalk of W l W has its last arc in its heart, so this last arc cannot be in a t-prefix. So we only need to build the hydrostructure on W l W if it contains s, as it is safe otherwise. These W l W can be enumerated in total O(mn) time.
Assuming no multiarcs, all the W l W that contain s form a tree because they are R-univocal. Since they all are different, with distinct leaf arcs they also have distinct head nodes. Thus, there exist total O(n) such walks, for which we use the two-pointer algorithm with the incremental hydrostructure to find its maximal safe subwalks. Note that if G has multiarcs, W l is clearly multiarc-free, and each parallel arc would form a distinct W (containing a single arc), where each such walk is equivalent in terms of safety. Thus, we use the two-pointer algorithm for all of them together, executing it only 1 time. As a result we get the following theorem.
Theorem D.3. The maximal k-st safe walks of a strongly connected graph G that are subwalks of trivial avertible 1-circular safe walks can be enumerated in O(mn) time plus O(n) executions of the two-pointer algorithm using the incremental hydrostructure variant for the specific model.
For F -covering, we need to make two fixes. Again, we only describe the algorithm for W l W , since for W W r it is symmetric. In the case where W l W does not contain s, in contrast to the E-covering models above, this does not guarantee its safety in all cases (see Theorem 5.1 (d) or Theorem E.3 (c)). From those walks we exclude those that contain t using O(n) two-pointer executions by the same argument as for s (as described above). Then we also exclude those that do not contain an F -arc in their heart, since these are safe if they do not contain s or t. Of the remaining walks W l W , only subwalks of W l can be safe, as the whole graph can be covered without using W by Lemma C.3. And since W l is maximal there can be at most n of such subwalks W l uniquely defined by their last node.
For those walks W l W that contain s and where W has parallel arcs (as described above), the safety is now only equivalent for two parallel arcs if they both are in F or both are not in F . Hence, in such a case, we execute the two-pointer algorithm twice, once for arcs in F and once for arcs not in F . We get the following theorem.
Theorem D.4. The maximal k-st F -covering safe walks of a strongly connected graph G that are subwalks of trivial avertible 1-circular safe walks can be enumerated in O(mn) time plus O(n) executions of the two-pointer algorithm using the incremental hydrostructure variant for the specific model.
The subset covering models reduce the covering constraint to only a subset F ⊆ E instead of the entire E. Note that this implies that any walk which is a solution in the E-covering model is also a solution in the F -covering model, but we can have walks which are not E-covering but F -covering. Thus, every F -covering safe walk is E-covering safe. Furthermore, if F is empty then no walk is safe, so in this section we assume F = ∅.
Note that, in contrast to the E-covering models, in the F -covering models, a single arc is not trivially safe. So in order to characterize their safety we extend the definition of hydrostructure for single arcs, by splitting the arc using a dummy node. Thus, a single arc can be treated as a walk with two arcs, for which the hydrostructure is already defined.
We call an arc in F an F -arc and a part of the graph F -covered if an F -arc belongs to it. Also, for a bridge-like walk, we define the F -covered SCCs, which are the maximal SCCs of its River, and the sea and cloud-related SCCs (see Lemma 3.4 (d)) that are F -covered. Similarly, for an avertible walk, the F -covered SCC is G. Furthermore, the F -covered sea and cloud-related SCCs are counted as one if they share all their F -arcs. Circular Models. A trivial walk W is circular safe if Heart(W ) is F -covered. For bridge-like walks, the issue with F -covering circular walks is that a set of cycles can cover the entire F if it is covered by some F -covered SCCs, making the walks unsafe. This is not possible if an arc in F exists outside the F -covered SCCs, or the number of such SCCs are more than k.
Theorem E.1 (Circular F -Covering Safety). For F ⊆ E a 1-circular safe walk W that contains at least two arcs is k-circular F -covering safe iff for the hydrostructure on W (for trivial) or Heart(W ) (for non-trivial) it holds that (a) k is less than the number of F -covered SCCs, or (b) there exists an F -covered arc in the River, that is not in any SCC of the River, or (c) W has an F -covered trivial heart.
Proof. (⇒) Assume that k is greater than or equal to the number of F -covered SCCs, there exists no F -covered arc in the River, that is not in any SCC of the River, and W does not have an F -covered trivial heart. We distinguish between W being trivial avertible, trivial bridge-like or non-trivial.
• If W is trivial and avertible but does not have an F -covered trivial heart, then by Lemma C.3 all arcs in F can be covered by a single circular walk without traversing Heart(W ). Thus, W is not k-circular F -covering safe.
• If W is trivial and bridge-like or non-trivial (in which case Heart(W ) is bridge-like by Theorem 4.1), then all arcs in F are in F -covered SCCs. Indeed arcs in the River are in F -covered SCCs by hypothesis; arcs in the Cloud or Sea are relatively in the F -covered cloud-related SCC or sea-related SCC; arcs in the Vapor of non-trivial walks are both in the sea-related SCC and cloud-related SCC; and for trivial walks the arcs in the Vapor that are neither in the cloud-related SCC nor in the sea-related SCC are in the trivial heart by definition, which does not contain arcs in F by hypothesis. Therefore, since all arcs in F are in F -covered SCCs and we have at most k F -covered SCCs of which none contains the whole walk W , it follows that F can be covered with k walks not having W as subwalk, hence W is not k-circular F -covering safe.
(⇐)
• If W has an F -covered trivial heart then it is k-circular F -covering safe.
• If k is less than the number of F -covered SCCs, then at least one solution walk needs to intersect two SCCs. We need to distinguish three cases: (A) if these are sea-related and cloud-related (in which case the sea-related SCC and the cloud-related SCC do not share all their F -arcs), (B) if one is in the River and the other is sea-related or cloud-related, or (C) if both are in the River. In all cases, Lemma 3.4 (e) implies that this solution walk needs to traverse from Sea to Cloud, which by Lemma 3.4 (a) implies the k-circular F -covering safety of W . In case (C) this is because the River is not strongly connected if there is more than one maximal SCC.
• If there exists an F -covered arc in the River, that is not in any SCC of the River, then the River is not strongly connected. Therefore, to cover this arc with a circular walk, the River needs to be exited and entered, which by Lemma 3.4 (e) implies that a solution walk covering this arc needs to traverse from Sea to Cloud, which by Lemma 3.4 (a) implies the k-circular F -covering safety of W .
Theorem E.4 (Wings of Non-Trivial k-st Safe Hearts). A non-trivial walk W l W W r , where W is its heart, W l its left and W r its right wing and where W contains at least two arcs is k-st F -covering safe iff W is k-st F -covering safe and (a) The F -arcs in R + s (W ) ∩ R − t (W ) ∩ River(W ) cannot be covered with k walks, or (b) Either both of s ∈ W l and t ∈ W r are false, or exactly one is true with:
• if s ∈ W l , then t / ∈ R + (W ) ∪ W r and F ⊆ R − t (W )∪ suffix of W l starting in s, and • if t ∈ W r , then s / ∈ R − (W ) ∪ W l and F ⊆ R + s (W )∪ prefix of W r ending in t.
Proof. Similar to the non-trivial hearts, not being able to cover the F -arcs of R + s (W ) ∩ R − t (W ) ∩ River(W ) with k walks ensures that one walk needs to exit and re-enter the river, making W safe along with its wings as such a walk goes from Sea(W ) to Cloud(W ) which completely contain the wings (by Lemma C.4) .
Also, s / ∈ W l and t / ∈ W r makes the wings safe if W is safe as they are R-univocal and univocal, respectively. They can also be safe with s ∈ W l , if we are required to separately cover the prefix of the left wing before s, and the location of t and the F -arcs does not allow the walk to end prematurely before covering the entire W l W W r . Note that if F is entirely contained in R − t (W ) and suffix of W l starting in s, F would be covered starting W l only from s itself, negating the above requirement making the wings not safe. Further, covering the entire W l W W r requires such a walk to have a subwalk from Sea(W ) to Cloud(W ) without ending before completing the right wing. This can be ensured by t / ∈ R + (W ) ∪ W r , else it can also end in Vapor(W ), Sea(W ) (as W is non-trivial) or before completely covering W r . By symmetry we have the corresponding criteria for t ∈ W r .
Implementation. The computation of F -covered SCCs, R + s (W ) and R − t (W ) clearly requires linear time in the size of the graph, i.e., O(m). The F walk-cover can be computed using flows in O(mn) time as described earlier. Furthermore, the number of executions of the two-pointer algorithm are still O(n) (see Theorem D.4). Thus, the time bounds for verification and simple enumeration algorithms does not change in the subset covering model. In the improved enumeration algorithm we need to additionally address maintaining R + s (W ), R − t (W ), and the size of the walk cover of R + s (W ) ∩ R − t (W ) ∩ River(W ) during the incremental computation procedure. Since by definition R + s (W ) (and R − t (W )) are the same as R + (W ) (and R − (W )) except for the source (and target) of the walks, we can use the same procedure (described in Section 6) to compute them incrementally in total O(m) time. Moreover, the subgraph R + s (W ) ∩ R − t (W ) ∩ River(W ) depends only on River(W ) and the location of s and t in it, so we can again use the same arguments (as described in Section 6) to prove that each arc enters and leaves this subgraph at most once during the incremental computation. Thus, the size of the F walk-cover can be maintained in O(m 2 ) time similar to the size of the walk-cover, resulting in the same bound as E-covering model.
Theorem E.5. The bounds of Theorem 6.3 also hold for the corresponding F -covering models.
In subset visibility we limit the solution of the problem to its visible arcs. We thus define vis F (W ) as the substring of a walk W which belongs to F . Note that this does not change the solution of the problem but only its representation, which is now limited to the visible set F . So if a walk W is a solution in the E-visible model for a problem, then we have vis F (W ) is a solution in the F -visible model for the problem, where F ⊆ E. Abusing notation we also simply say that W is a solution for the F -visible model of the problem. However, note that the safe solutions ignore the non-visible part of the walk to compute safety. For example Theorem 4.1 relaxes to the visible part of Vapor(Heart(W )) to being a single sequence of arcs (possibly disconnected). Henceforth, we shall continue to refer to such a sequence as a visible path despite being disconnected. Thus, relaxing the criteria for safety implies that even though F -visible solution for a problem is the same as the E-visible solution, we have every E-visible safe walk is F -visible safe but not vice-versa. As a result, in order to characterize the safety in Fvisible model, we relax the definition of the hydrostructure by relaxing the forward and backward reachability of a walk as follows:
Definition F.1. For a walk W where end(W ), start(W ) ∈ F , we define the restricted forward and backward F -visible reachability as
is not a subwalk of vis F (W )},
is not a subwalk of vis F (W )}.
Notice that the modified hydrostructure is merely more relaxed in terms of the Vapor. For the F -visible model, Lemma 3.3 relaxes the criteria of the Vapor being more than a single path, to having a single visible path (see Figure 6) . Similarly, the properties of the hydrostructure are adapted by considering vis F (W ) instead of W . Similarly, the visible wings of a walk W l F and W r F and the visible heart Heart F (W ) require visible splits and visible joins in terms of only visible arcs possibly having invisible arcs (or even subgraphs) between them. Thus, for arcs e, f ∈ F we consider (e, f ) as adjacent if there exists a path from head(e) to tail(f ) in G \ F . Implementation. In order to present the verification and enumeration algorithms for any model, it is sufficient to describe the computation of the hydrostructure. The only difference from Section 3 is that we shall now be using visible adjacency and hence visible splits and joins. In order to compute these efficiently we pre-compute all pairs reachability among endpoints of arcs in F in G \ F . This can be computed performing a traversal (BFS or DFS) from the k endpoints of arcs in F in O(mk) time, where k ≤ min(n, |F |). Thus, all the previous algorithms are adaptable in the F -visible model with an added expense of O(mn).
Theorem F.2. The bounds of Theorem 6.3 also hold for the corresponding F -visible models with an added O(mn) term.