# The Hydrostructure: a Universal Framework for Safe and Complete Algorithms
for Genome Assembly

Massimo Cairo Department of Computer Science, University of Helsinki, Finland,
<EMAIL_ADDRESS>Shahbaz
Khan *  — 11footnotemark: 1 This work was partially funded by the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No. 851093, SAFEBIO). Romeo Rizzi *  —
Department of Computer Science, University of Verona, Italy, Email:
<EMAIL_ADDRESS>Sebastian Schmidt *  — 11footnotemark: 1 22footnotemark:
2 Alexandru I. Tomescu *  — 11footnotemark: 1 22footnotemark: 2 This work was
partially funded by the Academy of Finland (grants No. 322595, 328877). Elia
C. Zirondelli 333 Our solutions for $k$-st safe for general $k$ requires the
query “is the size of a minimum walk-cover of a subgraph greater than $k$?”.
This can be answered using flows in $f=O(mn)$ time, and maintained during the
incremental computation in $g=O(m^{2})$ time, resulting in the stated bounds.
Considering them as black box algorithms, our bounds for verification,
enumeration and improved enumeration algorithm are $O(m+f)$, $O(m^{2}n+mnf)$
and $O(mn+o+ng)$ respectively. Department of Mathematics, University of
Trento, Italy, Email<EMAIL_ADDRESS>
###### Abstract

_Genome assembly_ is a fundamental problem in bioinformatics, requiring to
reconstruct a source genome from an _assembly graph_ built from a set of
_reads_ (short strings sequenced from the genome). Typically, in genome
assembly, a solution is considered to be an arc-covering walk of the graph.
Since assembly graphs admit many such solutions, a common approach is to find
what is definitely present in all solutions, known as _safe subsolutions_. For
example, most practical assemblers use _unitigs_ at the core of their
heuristics, namely paths whose internal nodes have unit in-degree and out-
degree, and which are clearly safe. The long-standing open problem of finding
_all_ the safe parts of the solutions was recently solved [RECOMB 2016]
yielding a 60% increase in contig length. This safe and _complete_ genome
assembly algorithm was followed by other works improving the time bounds, as
well as extending the results for different notions of assembly solution.
However, all such results typically used very specific approaches, which did
not generalise, and as a consequence could not handle practical issues. As
such, it remained open whether one can be _complete_ also for models of genome
assembly of practical applicability. Moreover, despite previous results
presenting _optimal_ algorithms, they were based on avoiding forbidden
structures (which are NO-certificates), and hence it was open whether there
exists any simple YES-certificate to complete the understanding of the problem
structure.

In this paper we present a _universal framework_ for obtaining safe and
complete algorithms unifying the previous results, while also allowing for
easy generalisations to incorporate many practical aspects. This framework is
based on an entirely new perspective for studying safety, and on a novel graph
structure (the _hydrostructure_) highlighting the reachability properties of
the graph from the perspective of a walk. The hydrostructure allows for simple
characterisations of safe walks in existing and new models for genome
assembly. Moreover, the hydrostructure serves as a simple YES-certificate for
all the studied models. We can directly adapt almost all our characterisations
to _optimal_ verification algorithms, and _simple_ enumeration algorithms.
Most of these enumeration algorithms are also improved to optimality using an
incremental computation procedure and an existing optimal algorithm for the
basic model [ACM Trans. Algorithms 2019, ICALP 2021].

On the theoretical side, we consider the hydrostructure as a generalisation of
the standard notion of a cut, giving a more flexible technique for studying
safety of many other types of covering walks of a graph. On the practical
side, we believe that the hydrostructure could prove to be a theoretical
breakthrough for a fundamental bioinformatics problem, leading also to an
improvement of _practical_ genome assembly from the point of view of
_completeness_.

##  1 Introduction

Most problems in Bioinformatics are based at their core on some theoretical
computational problem. After initial progress based on heuristics, several
such Bioinformatics problems witnessed a drastic improvement in their
practical solutions as a consequence of a breakthrough in their theoretical
foundations. A major example of this is how the FM-index [16] revolutionised
the problem of _read mapping_ , being central in tools such as [37, 36, 34].
Other such theoretical breakthroughs include computing quartet distance [15,
57] motivated by _phylogenetics_ , or fine-grained complexity lower bounds for
_edit distance_ computation [2] motivated by _biological sequence alignment_.
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, where all practical genome assemblers are fundamentally based on
heuristics. With our results we intend to fill exactly this gap and enable a
similar success story for practical genome assemblers, based on a theoretical
result at their core. Throughout this Introduction, we keep the Bioinformatics
details at a minimum, and we refer the reader to Appendix A for more practical
details and motivation.

##### State-of-the-art in genome assembly.

Given a collection of _reads_ (short strings sequenced from an unknown source
genome), the task is to reconstruct the source genome from which the reads
were sequenced. This is one of the oldest problems in Bioinformatics [49],
whose formulations range from a shortest common superstring of the reads [49,
30, 29], to various models of node- or arc-covering walks in different
_assembly graphs_ , encoding the overlaps between the reads (such as _de
Bruijn graphs_ [50], or _overlap graphs_ [43]) [51, 41, 42, 28, 26, 46, 44].
In general, most such theoretical formulations of different models of genome
assembly are NP-hard [32, 44, 46, 28]. However, a more fundamental theoretical
limitation is that such “global” problem formulations inherently admit a large
number of solutions [32], 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) [45, 38, 40].
Such a strategy commonly uses the assembly graph to find only the paths whose
internal nodes have _unit_ in- and out-degree (_unitigs_). Since unitigs do
not branch they are correct, and can be computed in linear time. The use of
unitigs dates back to 1995 [29] and is at the core of most state-of-the-art
genome assemblers, for both long reads (such as wtdbg2 [52]), and short reads
(such as MEGAHIT [35]). 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 [58].

##### 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 should be the basis of correct partial
answers to the genome assembly problem. In fact, various works [20, 5, 44, 53,
33, 6] presented the open question about the “assembly limit” (if any), or
formally, what is all that can be correctly assembled from the input reads, by
considering both graph theoretic and non-graph theoretic formulations. Unitigs
were first generalised in [51] by considering the paths having internal nodes
with unit out-degree (with no restriction on in-degree). These were later
generalised [42, 27, 32] 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 for a specific genome assembly formulation in a major
Bioinformatics venue [54] by introducing safe and complete algorithms for the
problem, described as follows.

Given a notion solution to a problem on a graph $G$ (i.e. some type of walk in
$G$), a partial solution (i.e. a walk $W$) is called _safe_ if it appears in
all solutions of the problem (i.e. $W$ is a subwalk of all solutions on $G$).
An algorithm reporting only 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 from the input reads.
Notions similar to safety were studied earlier in Bioinformatics [55, 11, 45],
and in other fields, including persistence [22, 13, 10], _$d$ -transversals_
[14], _$d$ -blockers_ [59], and _vital nodes/edges_ [4].

Given an assembly graph, the most basic notion of a solution (or a source
genome) is that of a closed (i.e. circular) walk covering all nodes or all
arcs at least once, thereby explaining their existence in the assembly graph
[54, 44, 46, 40, 45, 38, 32]. The safe walks for this notion of solution
include unitigs and their generalisations described above. Tomescu and
Medvedev [54] characterised the safe walks w.r.t. closed arc-covering walks as
omnitigs. 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, [54] presented an $O(m^{2}n)$-time algorithm111Trivial
analysis using new results about omnitigs proves $O(m^{2}n)$ time for [54],
though not explicitly stated. finding _all_ maximal safe walks for such genome
assembly solutions, in a graph with $m$ arcs and $n$ nodes. Later, Cairo et
al. [8] improved this bound to $O(mn)$, which they also proved to be optimal
by using graphs having $\Theta(mn)$-sized solutions. Recently, Cairo et al.
[9] presented a _linear-time_ output-sensitive algorithm for computing all
maximal omnitigs, using a compact representation of the safe walks, called
macrotigs.

##### Limitations of the existing theory of safe and complete algorithms.

Despite presenting optimal algorithms, a theoretical limitation of the
previous results from [54, 8, 1] is that safety is characterised in terms of
_forbidden structures_ (i.e. NO-certificates) for the safety of a walk. These
turned out to be an unnatural view on more advanced models of genome assembly,
where only a subset of the omnitigs is safe (see the next subsection). As
such, these characterisations were incomplete and unnatural in the absence of
easily verifiable YES-certificates. To illustrate this, consider for example
the classical notion of a _strong bridge_ $(x,y)$ (see Figure 1). Its NO-
certificate is a path from $x$ to $y$ avoiding $(x,y)$, which can thus be seen
as a forbidden path. The corresponding YES-certificate is a _cut_ between a
set of nodes $S$ (containing at least the nodes reachable from $x$ without
using $(x,y)$), and the remaining nodes $T$ (containing at least the nodes
reaching $y$ without using $(x,y)$), such that the only arc crossing the cut
is $(x,y)$. Such a certificate captures much more information about the
structure of the graph from the viewpoint of the arc $(x,y)$. We generalise
this idea from single arcs to walks to get a new perspective on safety
problems in genome assembly. For that, we use a similar graph structure (now
recognizing _safe_ walks) which is essentially a generalisation of a cut, and
hence a YES-certificate, which is described as follows.

Figure 1:  The perspective of a safe walk (bold black), generalizing a strong
bridge. Center: The strong bridge $(x,y)$ has a NO-certificate in form of a
forbidden path (red), and a YES-certificate in form of a cut between $S$ and
$T$ where $(x,y)$ is the only edge leaving $S$. Left: The NO-certificate of
the safety of the walk from $x$ to $y$ is a similar forbidden path (red).
Right: The YES-certificate of the safety of the walk from $x$ to $y$ is a
graph partition where $T$ is reachable from $S$ only by using the walk from
$x$ to $y$ contiguously.

Our perspective to study safety distinguishes between the trivial reason for
safety, i.e., the covering constraint of an arc (and the left and right
extensions the arc), from the more profound reason arising from the bridge-
like nature of some walks, which generalises the property of a strong bridge.
Such bridge-like walks are required to be traversed contiguously for
reachability between some nodes. Thus, analogous to NO-certificates of a
strong bridge (see Figure 1), a bridge-like walk (say from $x$ to $y$)
requires the absence of a forbidden path which allows reaching $y$ from $x$
without traversing the whole walk contiguously, as described in previous
results [54, 8, 1, 9]. Similarly, analogous to the YES-certificate of a strong
bridge (see Figure 1), a bridge-like walk has a directed cut-like structure
between the set of nodes $S$ reachable from $x$ without traversing the whole
walk, and the set of nodes $T$ reaching $y$ without traversing the whole walk.
Crossing the cut from $y$ to $x$ uses the remainder of the graph, which are
the nodes and edges outside the induced subgraphs of $S$ and $T$. On the other
hand, crossing the cut from $x$ to $y$ (or $S$ to $T$) requires traversing the
whole walk contiguously. This partitions the whole graph from the perspective
of the walk, reducing the requirement for the contiguous traversal of the
walk, to the simple requirement of reaching $y$ from $x$, allowing simpler
characterisations of more advanced models. Moreover, we can now use the same
YES-certificate for many different models, as opposed to finding a NO-
certificate separately for each model. Thus, our new perspective of a safe
walk as a generalisation of a strong bridge results in a universal approach
for the complete characterisation of safe walks.

##### Formulation of practically relevant genome assembly models.

Modeling a genome assembly solution as a single arc-covering walk is extremely
limiting in practice, due to the presence of multiple genomes in the sample
(not necessarily circular), sequencing errors or unsequenced genomic regions.
See Appendix A for further motivation of our definitions below, and a
discussion about how to handle practical aspects of the data such as
multiplicities (i.e. k-mer abundance).

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 _single_ closed arc-covering walk of the assembly graph, we
can change the model so that the solution is an _arc-covering_ collection of
up to $k\geq 2$ closed walks (i.e. every arc appears in some walk of the
collection). Further, for addressing _linear_ genomes, or unsequenced genomic
regions, we further change the model so that the solution is one _open_ arc-
covering walk from a given node $s$ to a given node $t$ (_$s$ -$t$ walk_), or
an arc-covering collection of up to $k\geq 2$ open $s$-$t$ walks. Moreover, if
there is no constraint $k$ on the number of walks in the collection, then we
will say that $k=\infty$.

######  Definition 1.1 ($k$-circular safe walk, $k$-st safe walk).

Let $G=V\cup E$ be a graph, let $s,t\in V$ and let $k\geq 1$. A walk $W$ is
called _$k$ -circular safe_ (or _$k$ -st safe_) if $W$ is a subwalk of at
least one walk of any arc-covering collection of up to $k$ circular walks (or
up to $k$ walks from $s$ to $t$).

######  Remark 1.2.

A graph admits an arc-covering collection of $k\geq 1$ circular walks if and
only if it is a disjoint union of at most $k$ strongly connected graphs. As
such, in the circular models we can assume the graph to be strongly connected.
In the linear models, we first solve the strongly connected case, and then
solve the cases $k=1,\infty$ for non-strongly connected graphs.

Further, the notion of genome assembly solution can be naturally extended to
handle sequencing errors. For example, the models can be extended so that the
collection of walks is required to cover only a _subset_ $F$ of the arcs (_$F$
-covering_). Another possible extension is to mark the erroneous arcs in
$E\setminus F$ as _invisible_ , in the sense that they are invisible when we
define safety (_$F$ -visible_, see below). These not only allow handling
errors, but also allow handling even more general notions of genome assembly
solutions through simple reductions (see Remark 1.4).

######  Definition 1.3 (Subset covering / visible).

Let $G=V\cup E$ be a graph, let $s,t\in V$, $F\subseteq E$, and let $k\geq 1$.
A walk $W$ is called:

  * •

_$k$ -circular $F$-covering safe_ (or _$k$ -st $F$-covering safe_) if $W$ is a
subwalk of at least one walk of every $F$-covering collection of up to $k$
circular walks (or up to $k$ walks from $s$ to $t$).

  * •

_$k$ -circular $F$-visible safe_ (or _$k$ -st $F$-visible safe_) if the
$F$-subsequence of $W$ occurs contiguously in the $F$-subsequence of at least
one walk of every arc-covering collection of up to $k$ circular walks (or up
to $k$ walks from $s$ to $t$). The _$F$ -subsequence_ of a walk is obtained by
removing its arcs _not in $F$_.

######  Remark 1.4.

The subset covering model can also solve a generalisation of the linear
models, where the walks in the collection can start and end in any node in
given _sets_ $S$ and $T$, respectively: set $F=E$, and add new nodes $s$ and
$t$ connected to / from all nodes in $S$ and $T$, respectively. Moreover, we
can also combine the subset covering and visibility models for some
$F,F^{\prime}\subseteq E$, to get _$F$ -covering $F^{\prime}$-visible safe
walks_, for both circular and linear models, and obtain analogous results (see
also Figure 2). By this, we can also solve the same models in a node-centric
formulation, where only (a subset of) the nodes are required to be covered
and/or visible: expand each node to an arc and choose only such node-arcs to
be covered and/or visible.

##  2 Contributions

We obtain safe and complete algorithms for a plethora of _natural_ genome
assembly formulations, as stated in Definitions 1.1 and 1.3 and Remark 1.4,
with an entirely new perspective, and a _universal framework_ for safety, the
_hydrostructure_ of a walk.

##### The Hydrostructure as a Universal Framework for safety.

The hydrostructure gives a more structured view of the graph from the
perspective of the walk, allowing for simple safety characterisation for _all_
models (see Figure 2). We characterise $k$-circular safe walks for any given
$k$ (where $1<k<\infty$), which was mentioned as an open problem in [1], and
prove the equivalence of the $k$-circular safe problems for all $k\geq 2$. We
also present the _first_ characterisations for the single and multiple linear
models (mentioned as open problems in [54]), which are in general harder
because the location of $s$ and $t$ affects safety. Moreover, the flexibility
of the hydrostructure allows us to generalise these to the more practically
relevant subset covering and visibility models.

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 may be of independent interest (see Section 4). It captures the bridge-
like characteristic of a walk for characterizing safety. This distinguishes
the core of a safe walk from its trivially safe extensions on both sides,
i.e., along the only way to reach it (its left wing, if exists), and along the
only way forward from it (its right wing, if exists). Its water-inspired
terminology stems from the standard notions of “source” and “sink” nodes, but
in the present case of a strongly connected graph now mimics the water cycle
on Earth [56]. The hydrostructure distinguishes the source part as
$\mathsf{Sea}$ and the target part as $\mathsf{Cloud}$. The internal part of
the bridge-like walk forms the $\mathsf{Vapor}$, which is the only way water
moves from $\mathsf{Sea}$ to $\mathsf{Cloud}$. On the other hand, water can
easily move from $\mathsf{Cloud}$ to $\mathsf{Vapor}$ and from
$\mathsf{Vapor}$ to $\mathsf{Sea}$. The rest of graph forms the
$\mathsf{River}$, which in general serves as an alternate route for the water
from $\mathsf{Cloud}$ to $\mathsf{Sea}$. For non-bridge-like walks the
hydrostructure trivially reduces to $\mathsf{Vapor}$ being the entire graph,
and the remaining components being empty. For any walk, we show that its
hydrostructure can be easily computed in linear time, by evaluating the
restricted reachability of the end points of the walk.

Figure 2: An overview of the characterisations of safety for non-trivial walks
in all our models. The arrow labeled EQ means equivalent criteria; an arrow
labeled OR means that the target characterization is the OR between the
criteria of the endpoints of the arrow; the arrow labeled MOD means
modification of the source characterization as described. For simplicity of
presentation, the criteria for trivial walks and wings (for linear models) are
not included, despite being simple criteria based on hydrostructure. Note that
all characterisations imply that the $\mathsf{Vapor}$ is a path, (otherwise
$\mathsf{Sea}$, $\mathsf{Cloud}$ and $\mathsf{River}$ would be empty, making
all the criteria trivially false) and hence include being $1$-circular safe.

##### Simple and _full_ characterisation for existing and new problems.

For single circular walks, the previous characterisations identified forbidden
paths [54, 8] resulting only in a NO-certificate. Our characterisation
simplifies it to merely $\mathsf{Vapor}$ not being the entire graph, which
basically signifies that the walk is bridge-like, resulting in easily
verifiable both YES- and NO-certificates. For $\infty$-circular safe walks,
the previous characterisation further requires the presence of a certificate
arc [1] forbidding cycles of certain types, resulting in a NO-certificate
which is even harder to verify than in the 1-circular model. Our
characterisation only adds an additional constraint of having a non-empty
$\mathsf{River}$, drastically simplifying the characterisation. Note that it
is the same for any given number $k\geq 2$ of closed walks, proving their
equivalence. See Section 5 for details.

For linear safe models, surprisingly every solution has to be $1$-circular
safe, allowing 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, $\mathsf{River}$ additionally has to be a single path, with some
criteria based on the location of $s$ and $t$. However, the multiple linear
model generalises the criteria on the $\mathsf{River}$ to be based on its
minimum walk-cover being of a certain size. Also, we require additional
characterisations for the safety of the wings, based on the reachability of
$s$ and $t$ in the candidate walk. See Section 6 for details. In the subset
covering model, the previous characterisations are easily extendable using
more concrete criteria involving the corresponding subset $F$. In the subset
visibility model, the hydrostructure itself is generalised for the
corresponding subset $F$, so that the existing characterisations can be
directly applied without any changes. Finally, for all these problems, the
hydrostructure itself (or in some cases with additional walk cover222For
simplicity we use the walk cover (a NO-certificate) in our characterisation,
which have a simple equivalent YES-certificate using maximum arc antichain.)
serves as both the YES- and NO-certificate. See Section 8 for details.

The simplicity of our characterisations motivates us to introduce the problem
of verifying whether a given walk is safe in a model. Despite this problem not
being explicitly studied earlier, the previous characterisations [54, 8, 1]
resulted in $O(mn)$ time verification algorithms, which again depend on the
corresponding certificate for the model. Recently, Cairo et al. [9] 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
characterisations are directly adaptable to linear time optimal verification
algorithms for almost all of our models, using simple techniques such as graph
traversal. See Footnote 3 for a comparison.

Safety | Previous Results | New Results
---|---|---
Problems | Verify | Enumerate | Verify | Enum. Trivial | Enum. Improved
$1$-circular | $O(mn)$ |  $O(m^{2}n)$ [54] | $O(m)^{*}$ | $O(m^{2}n)$ | -
| $O(mn)$ |  $O(mn)^{*}$ [8] |  |  |
| $O(m)^{*}$ |  $O(m+o)^{*}$ [9] |  |  |
$k$-circular | - | - | $O(m)^{*}$ | $O(m^{2}n)$ | $O(mn)^{*}$
$\infty$-circular | $O(mn)$ |  $O(m^{2}n)$ [1] | $O(m)^{*}$ | $O(m^{2}n)$ | $O(mn)^{*}$
$1$-st | - | - | $O(m)^{*}$ | $O(m^{2}n)$ | $O(mn+o)^{*}$
$k$-st | - | - | $O(mn)^{\\#}$ | $O(m^{2}n^{2})^{\\#}$ | $O(m^{2}n+o)^{\\#}$
$\infty$-st | - | - | $O(m)^{*}$ | $O(m^{2}n)$ | $O(mn+o)^{*}$
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 improved333 Our solutions for $k$-st safe for
general $k$ requires the query “is the size of a minimum walk-cover of a
subgraph greater than $k$?”. This can be answered using flows in $f=O(mn)$
time, and maintained during the incremental computation in $g=O(m^{2})$ time,
resulting in the stated bounds. Considering them as black box algorithms, our
bounds for verification, enumeration and improved enumeration algorithm are
$O(m+f)$, $O(m^{2}n+mnf)$ and $O(mn+o+ng)$ respectively. 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 using the same bounds and to
subset visibility with an additive $O(mn)$ term.

##### Novel techniques to develop optimal enumeration algorithms.

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 [8] and our new
characterisation, we not only improve upon [1] for $\infty$-circular walks,
but also make our $k$-circular safe algorithm optimal. In order to improve our
linear algorithms we present a novel technique to compute the hydrostructure
for all subwalks of a special walk using incremental computation. Since the
linear characterisations are built on top of the $1$-circular safe walks, we
use the concise representation of $1$-circular safe walks in $O(n)$ special
walks [9]. At its core, the incremental computation uses the incremental
reachability algorithm [24] requiring total $O(m)$ for each special walk.
Surprisingly, every node and arc can enter and leave $\mathsf{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,\infty$,
while for the general $k$ we also require to check if a subgraph can be
covered with $k$ walks. Moreover, we prove the optimality of our results
(except for _given_ $k$) by presenting a family of graphs having the size of
all maximal safe walks $\Omega(mn)$. See Footnote 3 for a comparison, and
Section 7 for further details.

Summarising, the hydrostructure is a mathematical tool which is flexible for
addressing a variety of models (handling different types of genomes, errors,
complex or unsequenced regions), and is adaptable to develop simple yet
efficient algorithms. Thus, we believe the various results of this paper can
form the theoretical basis of future _complete_ genome assemblers. We hope
that our paper together with [9] can enable the state-of-the-art genomic tools
to have advanced theoretical results at their core, as e.g. the FM-index in
read mapping tools, leading to similar success story for genome assembly.

##  3 Preliminaries

##### Graph Notations.

A _graph_ is a set $G=V\cup 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 $\textsc{tail}(e)$ of $e$, and
$v$ is the _head_ node $\textsc{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\in E$, we
denote $G\setminus e=V\cup E\setminus\\{e\\}$. In the rest of this paper, we
assume a fixed strongly connected graph $G=V\cup E$ which is not a cycle
444Safe walks in a cycle are not properly defined as they can repeat
indefinitely., with $|V|=n$ and $|E|=m>n$.

A _$w_{1}$ -$w_{\ell}$ walk_ (or simply _walk_) in $G$ is a non-empty
alternating sequence of nodes and arcs $W=(w_{1},\dots,w_{\ell})$, where for
all $1\leq i<\ell$: $\textsc{head}(w_{i})=w_{i+1}$ if $w_{i+1}$ is a node, and
$\textsc{tail}(w_{i+1})=w_{i}$ otherwise. Deviating from standard terminology,
if not otherwise indicated, $w_{1}$ and $w_{\ell}$ are _arcs_. We call
$\textsc{start}(W)=w_{1}$ the _start_ of $W$, and $\textsc{end}(W)=w_{\ell}$
the _end_ of $W$. $W$ is a _path_ if it repeats no node or arc, except that
$\textsc{start}(W)$ may equal $\textsc{end}(W)$.

A walk $W$ is called _closed_ if $\textsc{start}(W)=\textsc{end}(W)$ and
$\ell>1$, otherwise it is _open_. The notation $WW^{\prime}$ denotes the
concatenation of walks $W=(w_{1},\dots,w_{\ell})$ and
$W^{\prime}=(w^{\prime}_{1},\dots,w^{\prime}_{\ell^{\prime}})$, if
$(w_{1},\dots,w_{\ell},w^{\prime}_{1},\dots,w^{\prime}_{\ell^{\prime}})$ 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},\dots,z_{\ell},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. A walk $W$ that contains at least one element is _bridge-like_
if there exist $x,y\in G$ such that each $x$-$y$ walk contains $W$ as subwalk,
and otherwise it is called _avertible_. Observe that a bridge-like walk is an
open path.

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 [47, 31].

##### 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 $\textsc{head}(e)$ is a join node (or $\textsc{tail}(e)$ is a split
node). Two arcs $e$ and $e^{\prime}$ are _sibling arcs_ if
$\textsc{head}(e)=\textsc{head}(e^{\prime})$ or
$\textsc{tail}(e)=\textsc{tail}(e^{\prime})$. A walk
$W=(w_{1},\dots,w_{\ell})$ is _univocal_ if at most $w_{\ell}$ 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}WW^{r}$ where
$W^{l}\textsc{start}(W)$ is the longest R-univocal walk to $\textsc{start}(W)$
and $\textsc{start}(W)W^{r}$ is the longest univocal walk from
$\textsc{end}(W)$.

Figure 3: 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. The left
wing is from arc to node and the right wing from node to arc.

For a walk $W=w_{1},\dots,w_{\ell}$ 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_{\ell}$ if $W$ has no split arc. If $i\geq j$, then the _trivial
heart_ (or simply _heart_) $\mathsf{Heart}(W)$ of $W$ is its $w_{j}$-$w_{i}$
subwalk, and otherwise the _non-trivial heart_ (or simply _heart_)
$\mathsf{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}\mathsf{Heart}(W)W^{r}$. See Figure 3 for a
visualisation of these definitions.

Further, we use the following results from previous works in the literature.
The first result was used in [1, 9] (and possibly other previous works) even
though not stated explicitly.

######  Theorem 3.1 (restate = prelim, name = ).

For a strongly connected graph $G$ with $n$ nodes and $m$ arcs, the following
hold:

  1. (a)

_(Two-Pointer Algorithm[1, 9])_ Given a walk $W$ and a procedure $A$ to verify
the safety of its subwalks where all subwalks of a safe walk are safe, then
all the maximal safe subwalks of $W$ can be reported in $O(|W|f(m,n))$ time,
where each invocation of $A$ requires $f(m,n)$ time.

  2. (b)

_(Omnitig Bounds[8, 9])_ There are at most $m$ maximal $1$-circular safe walks
[8] where each has length of at most $O(n)$ [8] and of which $O(n)$ are non-
trivial [9], and the total length of all maximal $1$-circular safe walks in
$G$ is $O(mn)$ [8] (if $G$ is not a cycle).

  3. (c)

(Fault tolerant SCCs [19]) We can preprocess $G$ in $O(m)$ time, to report
whether $x$ and $y$ are in the same SCC in $G\setminus z$ in $O(1)$-time, for
any $x,y,z\in G$.

##  4 Hydrostructure

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 4.1.

The _restricted forward and backward reachability_ of a walk $W$ is defined as

  * •

$R^{+}(W)=\\{x\in G\mid\exists\text{ $\textsc{start}(W)$-$x$ walk
}W^{\prime}\text{s.t.~{}}W\text{ is not a subwalk of $W^{\prime}$}\\}$,

  * •

$R^{-}(W)=\\{x\in G\mid\exists\text{ $x$-$\textsc{end}(W)$ walk
}W^{\prime}\text{s.t.~{}}W\text{ is not a subwalk of $W^{\prime}$}\\}$.

By definition, all nodes and arcs of $W$ (except for its last arc
$\textsc{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 $\textsc{end}(W)\in 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 4(a)), we define the hydrostructure of a
walk as follows.

######  Definition 4.2 (Hydrostructure of a Walk).

Let $W$ be a walk with at least two arcs.

  * •

$\mathsf{Sea}(W)=R^{+}(W)\setminus R^{-}(W)$.

  * •

$\mathsf{Cloud}(W)=R^{-}(W)\setminus R^{+}(W)$.

  * •

$\mathsf{Vapor}(W)=R^{+}(W)\cap R^{-}(W)$.

  * •

$\mathsf{River}(W)=G\setminus(R^{+}(W)\cup R^{-}(W))$.

(a)

(b)

Figure 4: (a): The hydrostructure partitioning of a non-trivial heart $aZb$ in
the sets $\mathsf{Sea}$, $\mathsf{Cloud}$, $\mathsf{Vapor}$, and
$\mathsf{River}$ using $R^{+}(aZb)$ and $R^{-}(aZb)$. It also shows the
membership of the arcs, and the reachability among the parts. (b): The
hydrostructure for a trivial bridge-like walk $aZb$, with the sea-related and
cloud-related SCC shown using thick green cycles. The $\mathsf{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 $\mathsf{Sea}$, the only way to reach the $\mathsf{Cloud}$ is by
traversing the walk through the entire $\mathsf{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 $\mathsf{Sea}$ and
the $\mathsf{Cloud}$ that are separated by $W$ in the $\mathsf{Vapor}$.

On the other hand, a node or an arc from the $\mathsf{Cloud}$ can directly
reach the $\mathsf{Vapor}$ (by dissipation), being in $R^{-}(W)$, and from the
$\mathsf{Vapor}$ it can directly reach the $\mathsf{Sea}$ (by condensation),
being in $R^{+}(W)$. Finally, the $\mathsf{River}$ acts as an alternative path
from the nodes and arcs in the $\mathsf{Cloud}$ to the $\mathsf{Sea}$ (by
rainfall), since the forward reachability from the $\mathsf{Cloud}$ and the
backward reachability from the $\mathsf{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 $\mathsf{Vapor}$, whereas the
$\mathsf{Sea}$, $\mathsf{Cloud}$, and $\mathsf{River}$ are empty. On the other
hand, for a bridge-like walk, the $\mathsf{Vapor}$ is exactly the internal
path of the walk, resulting in the following important property for any walk
$W=aZb$.

######  Lemma 4.3 (restate = cloudcases, name = ).

For a walk $W$, $\mathsf{Vapor}(W)$ is the open path $Z$ iff $W$ is bridge-
like, otherwise $\mathsf{Vapor}(W)$ is $G$.

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 4(b) for the SCCs, and Figure 4(a) for reachability).

######  Lemma 4.4 (restate = clouds, name = ).

The hydrostructure on a bridge-like path $aZb$ exhibits the following
properties:

  1. a.

_(Safety)_ Every walk from $x\in\mathsf{Sea}(aZb)$ to
$y\in\mathsf{Cloud}(aZb)$ contains $aZb$ as a subwalk.

  2. b.

_(Avoidance)_ Every $x\in\mathsf{Cloud}(aZb)$ and $y\in\mathsf{Sea}(aZb)$ have
an $x$-$y$ walk with no subwalk $aZb$.

  3. c.

_(Separation)_ $a\in\mathsf{Sea}(aZb)$ and $b\in\mathsf{Cloud}(aZb)$.

  4. d.

_(SCCs)_ If $\mathsf{Sea}(aZb)$ is not just $\\{a\\}$, then
$\mathsf{Sea}(aZb)$ and the prefix of $aZb$ ending in its last split-node form
an SCC (denoted as _sea-related SCC_). Similarly, if $\mathsf{Cloud}(aZb)$ is
not just $\\{b\\}$, then $\mathsf{Cloud}(aZb)$ and the suffix of $aZb$
starting in its first join-node form an SCC (denoted as _cloud-related SCC_).

  5. e.

_(Reachability)_ Let $(x,y)\in G\times 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.

     * •

$(\mathsf{Vapor},\mathsf{Cloud})$ always where $y=b$, or
$(\mathsf{Sea},\mathsf{Vapor})$ always where $x=a$,

     * •

$(\mathsf{Cloud},\mathsf{Vapor})$ or $(\mathsf{Vapor},\mathsf{Sea})$, where
both always occur for non-trivial $aZb$,

     * •

$(\mathsf{Cloud},\mathsf{River})$ or $(\mathsf{River},\mathsf{Sea})$, where
both always occur for nonempty $\mathsf{River}$,

     * •

$(\mathsf{Cloud},\mathsf{Sea})$, where $aZb$ is univocal or R-univocal.

##### 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 $\textsc{start}(W)$
in $G\setminus\textsc{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 $\mathsf{Sea}$,
$\mathsf{Cloud}$, $\mathsf{Vapor}$ and $\mathsf{River}$ by processing each arc
and node individually (see Section E.1 for more details).

######  Theorem 4.5 (restate = hydrostructurebasicalgo, name = ).

The hydrostructure of any walk can be computed in $O(m)$ time.

##  5 Safety in Circular Models

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, because every
circular arc-covering walk contains all bridge-like walks by definition. If on
the other hand $\mathsf{Heart}(W)$ is avertible (having
$\mathsf{Vapor}(W)=G$), then a walk can cover the entire graph without having
$\mathsf{Heart}(W)$ as subwalk, making it unsafe by definition. Thus, the
characterisation for circular safe walks is succinctly described as follows
(see Appendix C for the proofs of this section):

[1-Circular]theoremonecircsafe A non-trivial walk $W$ is 1-circular safe iff
$\mathsf{Vapor}(\mathsf{Heart}(W))$ is a path.

Now, for $k\geq 2$, a single circular arc-covering walk can be repeated to get
$k$ circular arc-covering 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 5(a)) 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
$\mathsf{River}$ is not empty. Thus, we get the following characterisation.

[$k$-Circular]theoremkcircsafe A non-trivial walk $W$ is $k$-circular safe for
$k\geq 2$, iff $\mathsf{Vapor}(\mathsf{Heart}(W))$ is a path and
$\mathsf{River}(\mathsf{Heart}(W))$ is non-empty.

Notice that our characterisation does not distinguish between $k$ when $k\geq
2$, implying that all the problems of $(k\geq 2)$-circular safety are
equivalent. These characterisations can be directly adapted for an optimal
verification algorithm, by computing the hydrostructure for the given walk in
linear time. This also results in $O(m^{2}n)$ time enumeration algorithms
using the two pointer algorithm on a simple circular arc-covering walk of
length $O(mn)$ (see Section C.1). Moreover, using the optimal $O(mn)$ time
$1$-circular safe algorithm [8], 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 3.1 (b)) and using an
interesting property of $1$-circular safe walks that are not $k$-circular
safe. See Section C.1 for more details on the implementation.

(a)

(b)

Figure 5: (a) In the absence of the $\mathsf{River}$, the two cycles (shown in
thick green) can cover the cloud-related and sea-related SCCs of a non-trivial
$\mathsf{Heart}$ without having $aZb$ as subwalk. (b) The heart (green) and
the wings (violet and red) of an avertible walk $W=aZb$: $W$ is unsafe for
$s=s_{1}$ and $t=t_{1}$, because $\mathsf{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 $\mathsf{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}$.

lemmakcircularsubwalks Let $k\geq 2$. For a $1$-circular safe walk
$W=X\mathsf{Heart}(W)Y$ where $\mathsf{Heart}(W)=aZb$, if $W$ is not
$k$-circular safe then $XaZ$ and $ZbY$ are $k$-circular safe walks.

##  6 Safety in Linear Models

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
$\mathsf{Sea}$ to $\mathsf{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
5(b) for an example). We get the following characterisation (see Appendix D
for the proofs of this section).

######  Theorem 6.1 (name = $k$-st Safe Trivial Walks and Non-Trivial Hearts,
restate = linear).

A trivial walk $W$ (or a non-trivial heart $W$) is $k$-st safe iff it is a
single arc or

  1. (a)

$\mathsf{River}(W)$ cannot be covered with $k$ walks, or

  2. (b)

$s\notin R^{-}(W)$, or

  3. (c)

$t\notin R^{+}(W)$, or

  4. (d)

$W$ is trivial and some arc $e$ in $\mathsf{Heart}(W)$ is not $s$-$t$ suffix-
prefix covered in $W$.

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 $\mathsf{River}$ by Lemma 4.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 $\mathsf{Sea}$ of the heart a path and the $\mathsf{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 $\mathsf{Sea}$. We get
the following characterisation.

######  Theorem 6.2 (name = Wings of Non-Trivial $k$-st Safe Hearts, restate =
linearntwings).

A non-trivial $1$-circular safe walk $W^{l}WW^{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

  1. (a)

$\mathsf{River}(W)$ cannot be covered with $k$ walks, or

  2. (b)

either both of $s\in W^{l}$ and $t\in W^{r}$ are false, or exactly one is true
with:

     * •

if $s\in W^{l}$, then $t\notin R^{+}(W)\cup W^{r}$ and $s\notin W$, and

     * •

if $t\in W^{r}$, then $s\notin R^{-}(W)\cup W^{l}$ and $t\notin W$.

Note that the $k$-st safe problems are equivalent for all $k\geq 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)\in
O(mn)$, and further observe that for $k\geq m$ or $k=1$ we get $O(m)$. See
Section D.2 for more details on the implementation.

##  7 Incremental Computation of the Hydrostructure

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^{+}(\cdot)$, $R^{-}(\cdot)$ and the $\mathsf{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\in Zb$, and formally defined as
$R_{sib}^{+}(e):=\\{x\in G\mid\exists\text{ $\textsc{tail}(e)$-$x$ walk in
}G\setminus e\\}$. Formally we get the following (see Section E.2 for the
proofs of this paragraph).

######  Lemma 7.1 (restate = incrementalcloudsrepresentation, name = ).

Given a bridge-like walk $aZb$ it holds that
$R^{+}(aZb)=aZ\cup\bigcup_{\text{arc }e\in Zb}R_{sib}^{+}(e)$.

Additionally, since subwalks of bridge-like walks are bridge-like, the
following allows us to compute $R_{sib}^{+}(\cdot)$ incrementally along a
bridge-like walk.

######  Lemma 7.2 (restate = incrementalcloudscomputation, name = ).

Let $aZb$ be a bridge-like walk where $b$ is a split-arc and $e$ a split-arc
after $a$. Then

  1. (a)

$R_{sib}^{+}(e)\subseteq R_{sib}^{+}(b)$ and

  2. (b)

$R_{sib}^{+}(b)=R_{sib}^{+}(e)\cup\\{x\in G\mid\exists\text{ $e$-$x$ walk in
}G\setminus(R_{sib}^{+}(e)\cup\\{b\\})\\}$.

Hence, we can compute all $R^{+}_{sib}(\cdot)$ 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\in 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}^{+}(\cdot)$ before or with
$b$, or if $x\in aZ$.

##### Incremental Maintenance of the River Properties.

When using the two-pointer algorithm after computing the hydrostructure
incrementally, we can maintain properties of the $\mathsf{River}$ used
throughout the paper (Section 8). By Lemma 7.2 each node and arc enters
$R^{+}(\cdot)$ (and leaves $R^{-}(\cdot)$) 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 $\mathsf{River}$. The existence of the $\mathsf{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 $\mathsf{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
$\mathsf{River}$ is a path. Further, Lemma 7.2 also implies that entire SCCs
of the $\mathsf{River}$ (using both $R_{sib}^{+}(\cdot)$ and
$R^{-}_{sib}(\cdot)$) enter and leave the $\mathsf{River}$ at most once during
the execution of the two pointer algorithm. Hence, the SCCs of the
$\mathsf{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 $\mathsf{River}$ using the folklore fully dynamic
update algorithm for maximum flows [21] in $O(m)$ time per update. Since each
edge enters and leaves the $\mathsf{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
amortisation as follows. We execute the two-pointer algorithm on all maximal
$1$-circular safe walks (which we get in $O(mn)$ time from [8]), but only
maintain the hydrostructure and $\mathsf{River}$ properties for non-trivial
and bridge-like trivial $1$-circular safe walks (there are only $O(n)$ of
these by Theorem E.1 and they can be found in total $O(mn)$ time by Theorem
E.3 (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 Section D.3. Checking the walk-cover can be done as described above
for $k=1$ (maintain if the $\mathsf{River}$ is a path) or $k\geq 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.

######  Theorem 7.3.

Given a strongly connected graph with $m$ arcs and $n$ nodes, all the maximal
$k$-st safe walks can be reported in $O(mn+n\cdot f(m,n)+|out|)$ time, where
$f(m,n)$ is the time required for maintaining the size of the walk-cover
($f(m,n)=O(m)$ for $k=1$ or $k\geq m$, and $O(m^{2})$ otherwise), and $|out|$
is the size of the output.

Figure 6: A graph class with $\Theta(n)$ nodes and $m\in\Omega(n)\cap
O(n^{2})$ arcs. The bipartite graph has $m$ arcs, resulting in total
$\Theta(m)$ arcs. For each $i\in\\{1,\dots,m\\}$, $W_{i}=g_{1}\dots
g_{n}f_{e_{i}}e_{i}f^{\prime}_{e_{i}}g_{1}\dots g_{n}$ is $k$-circular safe
and $k$-st safe for each $k\geq 1$, and the total length of all $W_{i}$ is
$\Omega(mn)$. This example is adapted from [8].

The runtimes of $O(mn)$ are optimal because there exists a set of graphs (see
Figure 6) with safe walks in each model of total length $\Omega(mn)$. As
mentioned in Section D.2, the output size of the linear models is bounded by
$O(n^{3})$.

##  8 Safety for Subset Covering and Subset Visibility

In this section we give a short overview of safety in $F$-covering and
$F$-visible models where $F\subseteq E$. For a full discussion and formal
characterisation of these models, see Appendices F and G.

##### Subset covering.

For the purpose of this section we denote an arc in $F$ by _$F$ -arc_ and a
subgraph or walk containing an $F$-arc with the predicate _$F$ -covered_.
Similar to how only subwalks of 1-circular safe walks can be safe in
$E$-covering models, in subset covering only subwalks of walks that are safe
in an $E$-covering model can be safe in the corresponding $F$-covering model.
In the $F$-covering models, single arcs in $E\setminus F$ are not trivially
safe. So in order to characterise their safety, we split them using a dummy
node, since the hydrostructure is only defined on walks with at least two
arcs. Furthermore, if $F$ is empty, then no walk is safe, so in this section
we assume $F\neq\emptyset$.

In the _circular models_ , a trivial walk is safe if its heart is $F$-covered.
Further, for bridge-like walks (including trivial walks), we define the _$F$
-covered SCCs_ as the SCCs of the $\mathsf{River}$ as well as the sea- and
cloud-related SCCs (see Figure 4(b)) if they are $F$-covered. Then a bridge-
like walk is safe if any solution walk needs to leave an $F$-covered SCC,
since then it needs to complete a full cycle through the hydrostructure,
forcing it to have $W$ as subwalk. This is required if there is an $F$-arc
outside an SCC in the $\mathsf{River}$ or the number of $F$-covered SCCs is
greater than $k$. In all other cases, the walk is not safe.

In the _linear models_ , we define the restricted reachability of a walk $W$
from the point of view of $s$ and $t$ denoted by $R^{+}_{s}(W)$ and
$R^{-}_{t}(W)$. We define $R^{+}_{s}(W)$ as the subgraph that is reachable
from $s$ without using $W$ as subwalk and symmetrically $R^{-}_{t}(W)$ as the
subgraph that reaches $t$ without using $W$ as subwalk. Further, we refer to
the set $R^{+}_{s}(W)\cap R^{-}_{t}(W)$ as the _st-induced subgraph of $W$_
and to $R^{+}_{s}(W)\cap R^{-}_{t}(W)\cap\mathsf{River}(W)$ as the _st-induced
$\mathsf{River}$ of $W$_. Lastly, we define the _$F$ walk-cover_ of a graph as
a set of walks that cover all $F$-arcs in that subgraph.

With these definitions, we get a characterisation similar to that for the
corresponding $E$-covering model. We again characterise the non-trivial wings
separately, but here we describe only the characterisation of trivial walks
and non-trivial hearts. For the latter two, the conditions on the walk cover
of the $\mathsf{River}$ and the $s$-$t$ suffix-prefix covering of an arc in
the trivial heart are tightened: we substitute the walk cover with an $F$
walk-cover, and the arc in the trivial heart with an $F$-arc. The condition on
the location of $s$ and $t$ is tightened by excluding the case where all
$F$-arcs can be covered by $s$-$t$ walks without having $W$ as subwalk.

For the verification and enumeration algorithms, the sets $R^{+}_{s}(W)$ and
$R^{-}_{t}(W)$ can be computed similarly to $R^{+}(W)$ and $R^{-}(W)$ in the
same asymptotic time, and the $F$ walk-cover can be computed similarly to the
walk cover as well, again in the same asymptotic time. So all runtime bounds
for $E$-covering models apply also to the $F$-covering models.

##### Subset visibility.

In subset visibility, we limit the solution of a model to its visible arcs.
Thus we define $vis_{F}(W)$ as the subsequence 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 an $E$-visible model, then $vis_{F}(W)$ is a solution in the
corresponding $F$-visible model. Abusing notation we also simply say that $W$
is a solution for the $F$-visible model of the problem.

To employ the hydrostructure for subset visibility, we relax the definition of
the restricted reachabilities of a walk $W$. We define $R^{+}_{F}(W)$ as
everything reachable by a walk $W^{\prime}$ from $\textsc{end}(W)$ such that
$vis_{F}(W)$ is not a subwalk of $vis_{F}(W^{\prime})$, and symmetrically
$R^{-}_{F}(W)$ as everything that reaches $\textsc{start}(W)$ by a walk
$W^{\prime}$ such that $vis_{F}(W)$ is not a subwalk of $vis_{F}(W^{\prime})$.
With this modified definition of the hydrostructure, the condition for the
$\mathsf{Vapor}$ to be a path in Lemma 4.3 relaxes to the visible
$\mathsf{Vapor}$ being a path. Similarly, the other properties of the
hydrostructure are adapted by considering $vis_{F}(W)$ instead of $W$.

In subset visibility, arcs are considered adjacent if they are connected by an
invisible path. This new _visible_ adjacency can be precomputed in $O(mn)$
time, such that all algorithms for $E$-visible models can be directly adapted
to $F$-visible models with an added expense of $O(mn)$ time.

##  9 Conclusion

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 [54]. On genome assembly
graphs constructed from perfect data, omnitigs led to significantly 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 [54, 9, 1] is their
very problem-specific techniques, which seem extremely difficult to
generalise.

In this paper we presented an entirely new perspective to characterise 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\neq 1,\infty$ in non-strongly connected
graphs), and simple enumeration algorithms. We also improved our $k$-circular
safe and $k$-st safe (for $k=1,\infty$) algorithms to optimality using the
optimal $1$-circular safe algorithm [8] 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 _characterisations_ for the subset covering model, for all
$k$-circular safe and $k$-st safe problems. Moveover, we easily generalised
the _hydrostructure_ for the subset visibility model, so that the existing
characterisations 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 characterisations 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 [16] is now at the core of start-of-the-art read mapping
tools.

#### Acknowledgments

We thank Manuel A. Cáceres for helpful comments on the manuscript’s
introduction.

## References

  * [1] Nidia Obscura Acosta, Veli Mäkinen, and Alexandru I. Tomescu.  A safe and complete algorithm for metagenomic assembly.  Algorithms for Molecular Biology, 13(1):3:1–3:12, 2018.
  * [2] Arturs Backurs and Piotr Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51–58. ACM, 2015.
  * [3] Jørgen Bang-Jensen and Gregory Z Gutin.  Digraphs: Theory, Algorithms and Applications.  Springer Publishing Company, Incorporated, 2nd edition, 2008.
  * [4] Cristina Bazgan, Till Fluschnik, André Nichterlein, Rolf Niedermeier, and Maximilian Stahlberg.  A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths.  Networks, 73(1):23–37, 2019.
  * [5] Sébastien Boisvert, François Laviolette, and Jacques Corbeil.  Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies.  Journal of computational biology, 17(11):1519–1533, 2010.
  * [6] G. Bresler, M. Bresler, and D. Tse.  Optimal Assembly for High Throughput Shotgun Sequencing.  BMC Bioinformatics, 14(Suppl 5):S18, 2013.
  * [7] Terence A Brown.  The human genome.  In Genomes. 2nd edition. Wiley-Liss, 2002.
  * [8] Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi, and Alexandru I. Tomescu.  An Optimal _O_(_nm_) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph.  ACM Trans. Algorithms, 15(4):48:1–48:17, 2019.
  * [9] Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu, and Elia C. Zirondelli.  Genome assembly, from practice to theory: Safe, complete and linear-time.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 43:1–43:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [10] Katarína Cechlárová.  Persistency in the assignment and transportation problems.  Mat. Meth. OR, 47(2):243–254, 1998.
  * [11] Kun-Mao Chao, Ross C. Hardison, and Webb Miller.  Locating well-conserved regions within a pairwise alignment.  CABIOS, 9(4):387–396, 1993.
  * [12] Robert L Charlebois.  Organization of the prokaryotic genome.  ASM Press Washington DC, 1999.
  * [13] Marie Costa.  Persistency in maximum cardinality bipartite matchings.  Oper. Res. Lett., 15(3):143–9, 1994.
  * [14] Marie-Christine Costa, Dominique de Werra, and Christophe Picouleau.  Minimum $d$-blockers and $d$-transversals in graphs.  J. Comb. Optim., 22(4):857–872, 2011.
  * [15] Bartlomiej Dudek and Pawel Gawrychowski.  Computing quartet distance is equivalent to counting 4-cycles.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 733–743. ACM, 2019.
  * [16] Paolo Ferragina and Giovanni Manzini.  Opportunistic data structures with applications.  In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 390–398. IEEE Computer Society, 2000.
  * [17] Fabian Gärtner, Lydia Müller, and Peter F. Stadler.  Superbubbles revisited.  Algorithms Mol. Biol., 13(1):16:1–16:17, 2018.
  * [18] Hans R Gelderblom.  Structure and classification of viruses.  In Medical Microbiology. 4th edition. University of Texas Medical Branch at Galveston, 1996.
  * [19] Loukas Georgiadis, Giuseppe F Italiano, and Nikos Parotsidis.  Strong connectivity in directed graphs under failures, with applications.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1880–1899. SIAM, 2017.
  * [20] A. Guénoche.  Can we recover a sequence, just knowing all its subsequences of given length?  Computer Applications in the Biosciences, 8(6):569–574, 1992.
  * [21] Manoj Gupta and Shahbaz Khan.  Simple dynamic algorithms for maximal independent set and other problems.  CoRR, abs/1804.01823, 2018.
  * [22] P. L. Hammer, P. Hansen, and B. Simeone.  Vertices belonging to all or to no maximum stable sets of a graph.  SIAM Journal on Algebraic Discrete Methods, 3(4):511–522, 1982\.
  * [23] Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, and Fatima Vayani.  Popping superbubbles and discovering clumps: Recent developments in biological sequence analysis.  In Mohammad Kaykobad and Rossella Petreschi, editors, WALCOM: Algorithms and Computation - 10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings, volume 9627 of Lecture Notes in Computer Science, pages 3–14. Springer, 2016.
  * [24] Giuseppe F. Italiano.  Amortized efficiency of a path retrieval data structure.  Theor. Comput. Sci., 48(3):273–281, 1986.
  * [25] Giuseppe F Italiano, Luigi Laura, and Federico Santaroni.  Finding strong bridges and strong articulation points in linear time.  Theoretical Computer Science, 447:74–84, 2012.
  * [26] Iu, V. L. Florent’ev, A. A. Khorlin, K. R. Khrapko, and V. V. Shik.  Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides. A new method.  Doklady Akademii nauk SSSR, 303(6):1508–1511, 1988.
  * [27] Benjamin Grant Jackson.  Parallel methods for short read assembly.  PhD thesis, Iowa State University, 2009.
  * [28] Evgeny Kapun and Fedor Tsarev.  De Bruijn superwalk with multiplicities problem is NP-hard.  BMC Bioinformatics, 14(Suppl 5):S7, 2013.
  * [29] John D. Kececioglu and Eugene W. Myers.  Combinatorial algorithms for DNA sequence assembly.  Algorithmica, 13(1/2):7–51, 1995.
  * [30] John Dimitri Kececioglu.  Exact and approximation algorithms for DNA sequence reconstruction.  PhD thesis, University of Arizona, Tucson, AZ, USA, 1992.
  * [31] Valerie King, Satish Rao, and Rorbert Tarjan.  A faster deterministic maximum flow algorithm.  Journal of Algorithms, 17(3):447–474, 1994.
  * [32] Carl Kingsford, Michael C Schatz, and Mihai Pop.  Assembly complexity of prokaryotic genomes using short reads.  BMC bioinformatics, 11(1):1–11, 2010.
  * [33] Ka-Kit Lam, Asif Khalak, and David Tse.  Near-optimal assembly for shotgun sequencing with noisy reads.  BMC Bioinform., 15(S-9):S4, 2014.
  * [34] Ben Langmead and Steven L Salzberg.  Fast gapped-read alignment with bowtie 2.  Nature Methods, 9(4):357, 2012.
  * [35] Dinghua Li, Chi-Man Liu, Ruibang Luo, Kunihiko Sadakane, and Tak-Wah Lam.  Megahit: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de bruijn graph.  Bioinformatics, 31(10):1674–1676, 2015.
  * [36] Heng Li and Richard Durbin.  Fast and accurate short read alignment with Burrows–Wheeler transform.  Bioinformatics, 25(14):1754–1760, 2009.
  * [37] Ruiqiang Li, Chang Yu, Yingrui Li, Tak-Wah Lam, Siu-Ming Yiu, Karsten Kristiansen, and Jun Wang.  Soap2: an improved ultrafast tool for short read alignment.  Bioinformatics, 25(15):1966–1967, 2009.
  * [38] Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, and Alexandru I. Tomescu.  Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing.  Cambridge University Press, 2015.
  * [39] Julian R Marchesi.  Metagenomics: Current innovations and future trends.  Future Microbiology, 7(7):813–814, 2012.
  * [40] Paul Medvedev.  Modeling biological problems in computer science: a case study in genome assembly.  Briefings in bioinformatics, 20(4):1376–1383, 2019.
  * [41] Paul Medvedev and Michael Brudno.  Maximum likelihood genome assembly.  Journal of computational biology, 16(8):1101–1116, 2009.
  * [42] Paul Medvedev, Konstantinos Georgiou, Gene Myers, and Michael Brudno.  Computability of models for sequence assembly.  In WABI, pages 289–301, 2007.
  * [43] Eugene W. Myers.  The fragment assembly string graph.  In ECCB/JBI, page 85, 2005.
  * [44] Niranjan Nagarajan and Mihai Pop.  Parametric complexity of sequence assembly: theory and applications to next generation sequencing.  Journal of computational biology, 16(7):897–908, 2009.
  * [45] Niranjan Nagarajan and Mihai Pop.  Sequence assembly demystified.  Nature Reviews Genetics, 14(3):157–167, 2013.
  * [46] Giuseppe Narzisi, Bud Mishra, and Michael C Schatz.  On algorithmic complexity of biomolecular sequence assembly problem.  In Algorithms for Computational Biology, pages 183–195. Springer, 2014.
  * [47] James B Orlin.  Max flows in _O_(_nm_) time, or better.  In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Cpmputing, pages 765–774, 2013.
  * [48] Benedict Paten, Jordan M. Eizenga, Yohei M. Rosen, Adam M. Novak, Erik Garrison, and Glenn Hickey.  Superbubbles, ultrabubbles, and cacti.  J. Comput. Biol., 25(7):649–663, 2018.
  * [49] Hannu Peltola, Hans Söderlund, Jorma Tarhio, and Esko Ukkonen.  Algorithms for some string matching problems arising in molecular genetics.  In IFIP Congress, pages 59–64, 1983.
  * [50] P. A. Pevzner.  l-Tuple DNA sequencing: computer analysis.  Journal of Biomolecular Structure & Dynamics, 7(1):63–73, August 1989.
  * [51] Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman.  An Eulerian path approach to DNA fragment assembly.  Proceedings of the National Academy of Sciences, 98(17):9748–9753, 2001.
  * [52] Jue Ruan and Heng Li.  Fast and accurate long-read assembly with wtdbg2.  Nature Methods, 17(2):155–158, 2020.
  * [53] Ilan Shomorony, Samuel H. Kim, Thomas A. Courtade, and David N. C. Tse.  Information-optimal genome assembly via sparse read-overlap graphs.  Bioinform., 32(17):494–502, 2016.
  * [54] Alexandru I. Tomescu and Paul Medvedev.  Safe and complete contig assembly through omnitigs.  Journal of Computational Biology, 24(6):590–602, 2017.  Preliminary version appeared in RECOMB 2016.
  * [55] Martin Vingron and Patrick Argos.  Determination of reliable regions in protein sequence alignments.  Prot. Engin., 3(7):565–569, 1990.
  * [56] Wikipedia.  Water cycle, https://en.wikipedia.org/wiki/water_cycle, Accessed 2-Jun-2021.
  * [57] Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu.  Finding four-node subgraphs in triangle time.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1671–1680. SIAM, 2015.
  * [58] Fan Wu, Su Zhao, Bin Yu, Yan-Mei Chen, Wen Wang, Zhi-Gang Song, Yi Hu, Zhao-Wu Tao, Jun-Hua Tian, Yuan-Yuan Pei, Ming-Li Yuan, Yu-Ling Zhang, Fa-Hui Dai, Yi Liu, Qi-Min Wang, Jiao-Jiao Zheng, Lin Xu, Edward C. Holmes, and Yong-Zhen Zhang.  A new coronavirus associated with human respiratory disease in china.  Nature, 579(7798):265–269, 2020.
  * [59] Rico Zenklusen, Bernard Ries, Christophe Picouleau, Dominique de Werra, Marie-Christine Costa, and Cédric Bentz.  Blockers and transversals.  Discrete Mathematics, 309(13):4306–4314, 2009.

##  Appendix A Bioinformatics Motivation

Assuming we are sequencing a single circular genome (as when sequencing a
single bacterium), the most basic notion of a solution (or a source genome) is
that of a walk in the assembly graph covering all nodes or all arcs at least
once, thereby explaining their existence in the assembly graph [54]. Even if
the earlier works (mentioned in Section 1 on “global” genome assembly
formulations) include various _shortest_ versions of such walks (e.g.
Eulerian, Chinese postman, or even Hamiltonian), it is widely acknowledged
[44, 46, 40, 45, 38, 32] that a shortest walk misses repeats in the source
genome. Moreover, safe walks for _all_ arc-covering walks are also trivially
safe for more specialised types of walks. Both of these facts motivate the
lack of constraints of the solution walks, except than to require that they
are arc-covering.

However, such 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 real input data sets, as we explain next:

  * •

Assumption (i) is not practical for several reasons. When sequencing a
bacterium [12], one indeed obtains reads from a _single circular_ genome.
However, when sequencing all bacteria in an environmental sample (as in
_metagenomics_ [39]), the reads originate from _multiple circular_ genomes. In
case of a virus [18], the reads originate from a _single linear_ genome.
Finally, when sequencing eukaryotes such as human [7], the reads originate
from _multiple linear_ chromosomes.

  * •

Assumption (ii) is not practical because the sequencing process introduces
errors in the reads, with error rates ranging from 1% for short reads, up to
15% for long reads. Such read errors produce certain known structures in the
assembly graph [45], 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 generalisation to _superbubbles_ [23, 17, 48]),
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 that 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 [35], 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 [52] which
simply removes low abundance arcs.

  * •

Assumption (iii) is not 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.

Figure 7: 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 _arc-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=\textsf{AAT}$ and $t=\textsf{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.

The genome assembly models from Section 1 handle all such issues flexibly and
theoretically solid by considering _collections_ of closed or open walks. In
the subset covering models, 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. For example, marking bubbles as invisible prevents disrupting
the safety of their flanking regions. See Figure 7 for an example of these
models.

Note that in practice k-mer multiplicities are available with the genome data,
and these could be used to compute even longer safe paths when integrated into
our models. However this is beyond the scope of our paper, as they address a
fundamentally different graph problem, and may result in the following major
theoretical problems.

In case we use multiplicities to impose a coverage-goal for each arc,
specifying exactly how often a valid solution walk must contain an arc, then
the resulting theoretical formulation as a graph problem changes to a Eulerian
cycle, rather than simply an edge covering cycle. Practically, due to errors
in the data and varying abundance of different genomic regions, we may end up
with “non-Eulerian” nodes, i.e. nodes that must be entered more or less often
than they must be exited. Using another formulation, the above issue can be
addressed by allowing an interval of multiplicities for each arc, where the
existence of a valid solution walk obeys these interval restrictions. However,
this can be reduced555Assign the closed interval $[0,1]$ to each arc, and
$[1,1]$ to each node $v$ extended as an arc $(v_{in},v_{out})$, where all
incoming arcs of $v$ are incident on $v_{in}$ and the outgoing arcs of $v$
leave from $v_{out}$. to the Hamiltonian circuit problem which is NP-Hard. Our
models address the information on k-mer abundances using subset covering and
visibility, loosing out on some information to avoid modifying the underlying
graph problem.

##  Appendix B Omitted Hydrostructure Proofs

*

###### Proof.

We decompose $W$ into $aZb$, where $a$ and $b$ are arcs. We first prove that
if $\mathsf{Vapor}(aZb)$ is not exactly the open path $Z$, then
$\mathsf{Vapor}(aZb)=G$ and $aZb$ is avertible. Assume that $Z$ is not an open
path, or $\mathsf{Vapor}(aZb)$ contains a node or arc $x\notin 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\notin\\{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\setminus Z$ without
containing $aZb$. By definition, the walk $Z$ is in $\mathsf{Vapor}(aZb)$ as
well. So $R^{+}(aZb)=G$, and by symmetry one can prove that $R^{-}(aZb)=G$, so
$\mathsf{Vapor}(aZb)=G$. This also makes $aZb$ avertible, since, for any pair
$x,y\in 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 $\mathsf{Vapor}(aZb)$ is an open path equal to $Z$, then
$aZb$ is bridge-like. Since $Z$ is an open path, $b\notin Z$ else it would
repeat the node $\textsc{tail}(b)$. However, $b\in R^{-}(aZb)$ by definition,
so we have $b\notin R^{+}(aZb)$, which means $aZb$ is bridge-like because of
the pair $(a,b)$. ∎

*

###### Proof.

We prove the statements in reverse order for simplicity.

  * (e)

We first prove all the incident pairs involving the $\mathsf{River}(aZb)$, and
then the residual pairs involving the $\mathsf{Vapor}(aZb)$, and finally
between $\mathsf{Sea}(aZb)$ and $\mathsf{Cloud}(aZb)$.

    * –

We show that $x,y\in(\mathsf{River},\mathsf{Vapor})$ and
$x,y\in(\mathsf{River},\mathsf{Cloud})$ do not exist. Since
$x\in\mathsf{River}(aZb)$, it holds that $x\notin R^{+}(aZb)$ and therefore
$x\neq a$. Thus, $y\in R^{-}(aZb)$ (and hence $\mathsf{Vapor}(aZb)$ or
$\mathsf{Cloud}(aZb)$), implies $x\in R^{-}(aZb)$ because of $(x,y)$, as
prepending $x$ ($\neq a$) does not make $aZb$ a subwalk. This contradicts that
$x\in\mathsf{River}(aZb)$ by definition. By symmetry
$x,y\in(\mathsf{Vapor},\mathsf{River})$ and
$x,y\in(\mathsf{Sea},\mathsf{River})$ do not exist as well.

    * –

For $x,y\in(\mathsf{Vapor},\mathsf{Cloud})$ we necessarily have $y=b$, because
$x\in R^{+}(aZb)$ would otherwise add $y\in R^{+}(aZb)$, removing it from
$\mathsf{Cloud}(aZb)$. When $y=b$ we get $aZb$ as a subwalk, preventing
$R^{+}(aZb)$ from covering $y$. By symmetry,
$x,y\in(\mathsf{Sea},\mathsf{Vapor})$ implies $x=a$.

    * –

We show that $x,y\in(\mathsf{Sea},\mathsf{Cloud})$ implies $x=a$ and $y=b$,
which contradicts our definition of $aZb$ as being from arc to arc. This is
because $x\in R^{+}(aZb)$ would add $y\in R^{+}(aZb)$ if $y\neq b$, as
described above, and symmetrically $y\in R^{-}(aZb)$ implies $x=a$.

Let $x,y\in(\mathsf{Cloud},\mathsf{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\in R^{-}(aZb)$ but $y\notin 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=\textsc{head}(b)$, let $W$ be such a walk of minimum length. But then,
since $y\notin 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 $\mathsf{Sea}(aZb)\neq\\{a\\}$, then for every node and arc
$x\in\mathsf{Sea}(aZb)$ with $x\neq a$ there is a path $P$ in
$\mathsf{Sea}(aZb)$ containing $x$ which starts from an arc $e$ with
$\textsc{tail}(e)\in\mathsf{Vapor}(aZb)$ and ends in $a$. Notice that
$\textsc{tail}(e)$ is a split-node, since $P$ _diverges_ from $aZb$ at $e$,
ensuring that $\textsc{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\neq a$
within $W^{P}\cup\mathsf{Sea}(aZb)$, because the path would leave $aZb$ latest
at its last split node to enter $\mathsf{Sea}(aZb)$ (using Lemma 4.4 (e)). And
this will also prove the second part by symmetry.

For a node or an arc $x\neq a$ in $\mathsf{Sea}(aZb)$, by definition there is
an $a$-$x$ walk inside $R^{+}(aZb)$ that does not have $aZb$ as subwalk.
Starting from $\textsc{head}(a)\in\mathsf{Vapor}(aZb)$ this walk exits
$\mathsf{Vapor}(aZb)$ into the $\mathsf{Sea}(aZb)$ (since
$R^{+}(aZb)=\mathsf{Vapor}(aZb)\cup\mathsf{Sea}(aZb)$), with an arc $e$ having
$\textsc{tail}(e)\in\mathsf{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 $\mathsf{Sea}(aZb)$ because the only
arc leaving $\mathsf{Sea}(aZb)$ is $a$, by Lemma 4.4 (e).

This also proves that there exists such a circular path for $a$ if there
exists some $x\in\mathsf{Sea}(aZb)\neq a$. For $\mathsf{Sea}(aZb)=a$, we have
no split nodes on $aZb$ because $R^{+}(aZb)$ does not leave $aZb$. This makes
$W^{P}=\emptyset$ resulting in no SCC.

  * (c)

By definition, $a\in R^{+}(aZb)$ and $a\notin R^{-}(aZb)$ when $aZb$ is
bridge-like, resulting in $a\in\mathsf{Sea}(aZb)$. Symmetrically, we prove
$b\in\mathsf{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 $\mathsf{Sea}(aZb)=\\{a\\}$, then $y=a$,
making $P$ a path from $x$ to $y$ without having $aZb$ as subwalk. Otherwise,
by Lemma 4.4 (d), there is a path from $a$ to every such
$y\in\mathsf{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 $\mathsf{Sea}(aZb)$ from $\mathsf{Cloud}(aZb)$ is
through $\mathsf{Vapor}(aZb)$ (by Lemma 4.4 (e)) so every path from
$\mathsf{Sea}(aZb)$ to $\mathsf{Cloud}(aZb)$ passes through
$\mathsf{Vapor}(aZb)$. Further, $\mathsf{Vapor}(aZb)$ can only be entered from
$\mathsf{Sea}(aZb)$ through $a$ (by Lemma 4.4 (e)) and can only be exited to
$\mathsf{Cloud}(aZb)$ through $b$ (by Lemma 4.4 (e)), and every such path
contains the entire $aZb$ as subwalk (by Lemma 4.3). ∎

##  Appendix C Safety in Circular Models

As described in Section 5, since trivial walks are naturally safe the
characterisations are stated only for non-trivial walks.

*

###### Proof.

$(\Rightarrow)$ Let $\mathsf{Vapor}(\mathsf{Heart}(W))$ not be a path. Let
$aZb:=\mathsf{Heart}(W)$, $a^{\prime}$ be a sibling join arc of $a$ and
$b^{\prime}$ be a sibling split arc of $b$. Then, by Lemma 4.3, $aZb$ is
avertible. We prove that $aZb$ is not $1$-circular safe by constructing a
circular arc-covering walk $\mathcal{C}$ that does not contain $aZb$. Let $P$
be an $a^{\prime}$-$b^{\prime}$ walk, such that $aZb$ is not a subwalk of $P$,
which exists exactly because $aZb$ is avertible (if it does not exist, then
$a^{\prime}$ and $b^{\prime}$ would make $aZb$ a bridge-like walk). Let
$\mathcal{C^{\prime}}$ be an arbitrary circular arc-covering walk of $G$. If
$\mathcal{C^{\prime}}$ does not contain $aZb$ the claim holds, otherwise
consider $\mathcal{C}$ obtained from $\mathcal{C^{\prime}}$, by replacing
every $aZb$ subwalk with $aZPZb$. Concluding, since $aZb$ is not $1$-circular
safe, it holds that $W$ is not $1$-circular safe.

$(\Leftarrow)$ Let $\mathsf{Vapor}(\mathsf{Heart}(W))$ be a path. Then
$\mathsf{Vapor}(\mathsf{Heart}(W))$ is not the whole $G$. Moreover, by Lemma
4.3, $\mathsf{Heart}(W)$ is bridge-like, so there are $x,y\in G$ such that
each $x$-$y$ walk has $\mathsf{Heart}(W)$ as a subwalk. Therefore, since every
circular arc-covering walk $\mathcal{C}$ in $G$ contains both $x$ and $y$ and
hence a subwalk from $x$ to $y$, $\mathsf{Heart}(W)$ is a subwalk of
$\mathcal{C}$ (and hence $1$-circular safe). Further, since $\cal C$ is
circular, the whole $W$ is $1$-circular safe, as $\mathsf{Heart}(W)$ can only
be traversed by also passing through its univocal extension. ∎

*

###### Proof.

$(\Rightarrow)$ We first prove that $W$ is not $k$-circular safe if
$\mathsf{Vapor}(\mathsf{Heart}(W))$ is not a path or
$\mathsf{River}(\mathsf{Heart}(W))$ is empty.

  * •

If $\mathsf{Vapor}(\mathsf{Heart}(W))$ is not a path, then using Section 5 $W$
is not $1$-circular safe, or there is a circular arc-covering walk
$\mathcal{C}$ not containing $W$. Thus, a collection of $k$ copies of
$\mathcal{C}$ is also arc-covering not containing $W$, proving that $W$ is not
$k$-circular safe.

  * •

If $\mathsf{Vapor}(\mathsf{Heart}(W))$ is a path, and
$\mathsf{River}(\mathsf{Heart}(W))$ is empty, we can prove that $W$ is not
$k$-circular safe for $k\geq 2$ because for a non-trivial $W$ it holds that
$\mathsf{Cloud}(\mathsf{Heart}(W))\cup\mathsf{Vapor}(\mathsf{Heart}(W))$ and
$\mathsf{Sea}(\mathsf{Heart}(W))\cup\mathsf{Vapor}(\mathsf{Heart}(W))$ are
each strongly connected. Thus, two different walks can separately cover them
as $\mathsf{River}(\mathsf{Heart}(W))$ is empty.

We only prove that
$\mathsf{Cloud}(\mathsf{Heart}(W))\cup\mathsf{Vapor}(\mathsf{Heart}(W))$ is
strongly connected as the other follows by symmetry. Since $W$ is non-trivial,
$\mathsf{Heart}(W)$ starts with a join arc $a$ and ends with a split arc $b$.
If $\mathsf{Cloud}(\mathsf{Heart}(W))=\\{b\\}$ then clearly it is the join
sibling of $a$, making
$\mathsf{Cloud}(\mathsf{Heart}(W))\cup\mathsf{Vapor}(\mathsf{Heart}(W))$ a
cycle and hence strongly connected. Otherwise, if
$\mathsf{Cloud}(\mathsf{Heart}(W))\neq\\{b\\}$ then the strong connectivity
follows by Lemma 4.4 (d).

$(\Leftarrow)$ If $\mathsf{Vapor}(\mathsf{Heart}(W))$ is a path then
$\mathsf{Heart}(W)$ is bridge-like by Lemma 4.3. If
$\mathsf{River}(\mathsf{Heart}(W))$ is not empty, since the graph is strongly
connected we can enter $\mathsf{River}(\mathsf{Heart}(W))$ only from
$\mathsf{Cloud}(\mathsf{Heart}(W))$ (by Lemma 4.4 (e)) using some arc. Hence,
every walk covering this arc requires a subwalk from
$\mathsf{River}(\mathsf{Heart}(W))$ to $\mathsf{Cloud}(\mathsf{Heart}(W))$,
which passes through $\mathsf{Sea}(\mathsf{Heart}(W))$ (by Lemma 4.4 (e)).
Using Lemma 4.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
$\mathsf{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^{\prime}$ of $b$. We claim that for any such sibling $b^{\prime}$, we have
$b^{\prime}\in\mathsf{River}(aZ^{*}b^{*})$, which is equivalent to
$b^{\prime}\notin R^{+}(aZ^{*}b^{*})\cup R^{-}(aZ^{*}b^{*})$.

Now, $aZ$ is bridge-like (since $aZb$ is bridge-like), so each
$\textsc{start}(aZ)$-$\textsc{end}(aZ)$ walk has $aZ$ as subwalk. Since
$\textsc{end}(aZ)=\textsc{tail}(b^{\prime})$ it follows that each
$a$-$b^{\prime}$ walk has $aZ$ as subwalk, and hence its prefix $aZ^{*}b^{*}$.
Thus, $b^{\prime}\notin R^{+}(aZ^{*}b^{*})$. Further, we know that
$b^{\prime}\in\mathsf{Sea}(aZb)$ as it is surely in $R^{+}(aZb)$ (by
definition) and not in $\mathsf{Vapor}(aZb)$ (for bridge-like $aZb$ by Lemma
4.3). So any path from $b^{\prime}$ to $b^{*}\in\mathsf{Vapor}(aZb)$ surely
enters $\mathsf{Vapor}(aZb)$ through $a$ (by Lemma 4.4 (e)). Hence it has
$aZ^{*}b^{*}$ as a subwalk since $\mathsf{Vapor}(aZb)$ is a path and
$aZ^{*}b^{*}$ is a prefix of $aZb$. Thus, $b^{\prime}\notin
R^{-}(aZ^{*}b^{*})$.

Thus $b^{\prime}\notin(R^{+}(aZ^{*}b^{*})\cup R^{+}(aZ^{*}b^{*}))$ implying
that $b^{\prime}\in\mathsf{River}(aZ^{*}b^{*})$, and by Section 5 that
$aZ^{*}b^{*}$ is $k$-circular safe. Therefore, since
$\mathsf{Heart}(XaZ)=aZ^{*}b^{*}$, we conclude that $XaZ$ is $k$-circular
safe. By symmetry $ZbY$ is also $k$-circular safe. ∎

###  C.1 Implementation

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 4.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 3.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 3.1 (b)). Computing
their hydrostructure in $O(m)$ time either verifies them to be $k$-circular
safe or its two subwalks as $k$-circular safe (using Figure 5). Hence, using
the $O(mn)$ time optimal $1$-circular safe algorithm [8] we get the following
result.

######  Theorem C.1.

Given a strongly connected graph with $m$ arcs and $n$ nodes, all the maximal
$k$-circular safe walks can be reported in $O(mn)$ time.

##  Appendix D Safety in Linear Models

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 D.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\notin Z$ (or $t\notin Z$). Recall that $Z$ starts and ends with a node.

######  Definition D.2 ($s$-$t$ Suffix-Prefix Covering).

An arc $e\in 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 D.3.

For a trivial avertible walk $aZb$ in a strongly connected graph $G$, the
graph $G\setminus\mathsf{Heart}(aZb)$ is also strongly connected.

###### Proof.

Observe that since $\mathsf{Heart}(aZb)$ is from arc to arc and
$\mathsf{Heart}(aZb)$ is a biunivocal path, removing $\mathsf{Heart}(aZb)$
from $G$ does not remove any endpoint of remaining arcs. For any two nodes
$x,y$ in $G\setminus\mathsf{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\setminus\mathsf{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 characterise the safety of the
wings of non-trivial walks.

*

###### Proof.

If $W$ is a single arc, it is trivially safe. Otherwise, let $W=aZb$ where $a$
and $b$ are arcs.

$(\Rightarrow)$ When the conditions (a), (b), (c) and (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 D.3 there exists an
arc-covering circular walk $\mathcal{W}$ in $G\setminus\mathsf{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 $\mathsf{Heart}(aZb)$ are
$s$-$t$ suffix-prefix covered in $aZb$, this walk covers all the arcs of
$\mathsf{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 Section 5. 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\in R^{-}(aZb)$ and $t\in
R^{+}(aZb)$, an $s$-$t$ walk can cover the cloud-related SCC and the sea-
related SCC (Lemma 4.4 (d)), necessarily covering $\mathsf{Cloud}(aZb)$ and
$\mathsf{Sea}(aZb)$. For a non-trivial heart it then also covers
$\mathsf{Vapor}(aZb)$. For trivial walks, all arcs in $\mathsf{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,
$\mathsf{River}(aZb)$ can be completely covered by the $k$ walks between
$\mathsf{Cloud}(aZb)$ and $\mathsf{Sea}(aZb)$, because (a) is false. Hence,
$G$ can be covered without going from $\mathsf{Sea}(aZb)$ to
$\mathsf{Cloud}(aZb)$ and, therefore, without having $aZb$ as a subwalk. Thus,
$aZb$ is not $k$-st safe.

$(\Leftarrow)$ If $\mathsf{River}(aZb)$ cannot be covered with $k$ walks, then
to cover $\mathsf{River}(aZb)$ at least one walk needs to enter
$\mathsf{River}(aZb)$ twice. This ensures that it has a subwalk from
$\mathsf{Sea}(aZb)$ to $\mathsf{Cloud}(aZb)$ and hence $aZb$ (by Lemma 4.4
(a)). If $s\notin R^{-}(aZb)$, then the only way to cover $b$ (and
$\mathsf{Cloud}(aZb)$) is through a walk from $\mathsf{Sea}(aZb)$ to
$\mathsf{Cloud}(aZb)$, necessarily having $aZb$ as subwalk (by Lemma 4.4 (a)).
This can be symmetrically proven for $t\notin R^{+}(aZb)$. Finally, if $aZb$
is a trivial walk with an arc in $\mathsf{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 D.4.

A non-trivial $1$-circular safe walk $W^{l}WW^{r}$ with
$W=\mathsf{Heart}(W^{l}WW^{r})$ has $W^{l}$ in $R^{+}(W)$ and $W^{r}$ in
$R^{-}(W)$.

###### Proof.

Since $W^{l}WW^{r}$ is non-trivial, $W$ is non-trivial and therefore
$\mathsf{Sea}(W)\neq\\{\textsc{start}(W)\\}$ from which by Lemma 4.4 (d)
follows that $\mathsf{Sea}(W)$ with some part of $\mathsf{Vapor}(W)$ forms an
SCC. But then, every R-univocal walk ending in $\textsc{start}(W)$ is in
$\mathsf{Sea}(W)\cup\mathsf{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)$. ∎

*

###### Proof.

If the $\mathsf{River}(W)$ has cannot be covered with $k$ walks, then to cover
it using only $k$ solution walks at least one walk enters $\mathsf{River}(W)$
twice. By Lemma 4.4 (a) and (e) this walk makes $W^{l}WW^{r}$ safe as its
subwalk necessarily goes from $\mathsf{Sea}(W)$ to $\mathsf{Cloud}(W)$ which
completely contain the wings (by Lemma D.4).

Now, the wings are also safe if $s\notin W^{l}$ and $t\notin W^{r}$, as they
are univocal extensions. They can also be safe with $s\in 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}WW^{r}$. Note that if $s\in W^{l}\cap 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}WW^{r}$ requires such a
walk to have a subwalk from $\mathsf{Sea}(W)$ to $\mathsf{Cloud}(W)$ without
ending before completing the right wing. This can be ensured by $t\notin
R^{+}(W)\cup W^{r}$, else it can also end in $\mathsf{Vapor}(W)$,
$\mathsf{Sea}(W)$ (as $W$ is non-trivial) or before completely covering
$W^{r}$. By symmetry we have the corresponding criteria for $t\in W^{r}$. ∎

###  D.1 Non-Strongly Connected Graphs

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 D.5.

Let $G=V\cup E$ be a graph, and let $s,t\in V$. It holds that $G$ admits an
$s$-$t$ arc-covering 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 D.5. This allows us to decompose
the graph into a sequence $D:=(S_{1},e_{1},S_{2},\dots,e_{\ell-1},S_{\ell})$
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^{\prime}$-$t^{\prime}$ arc-covering walks in $S_{i}$, where $s^{\prime}$
and $t^{\prime}$ 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 D.6 below), solving this special case.

We define the _inter-SCC univocal extension_ $U^{\prime}(e)$ of an inter-SCC
arc $e$ as a walk $XYZ$ 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 $\textsc{start}(Y)$ that is R-univocal in the SCC of
$\textsc{tail}(\textsc{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 $\textsc{start}(X)$. And third, $Z$ is the longest walk
starting in $\textsc{end}(Y)$ that is univocal in the SCC of
$\textsc{head}(\textsc{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 $\textsc{end}(Z)$. We get the following characterisation:

######  Theorem D.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:

  1. (a)

it is a subwalk of the inter-SCC univocal extension of an inter-SCC arc, or

  2. (b)

it is 1-s’t’ safe in an SSC $S$ of $G$, where $s^{\prime}$ is the entry point
of $S$, and $t^{\prime}$ 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^{\prime}(e)=XYZ$ of an inter-SCC arc $e$, we prove that $XYZ$ 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 $XYZ$ follows by symmetry. By definition, $Z$ is in a single SCC
$S$ and $\textsc{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 $XYZ$ each solution walk needs to traverse
$Z$, which proves the safety of $YZ$, and by symmetry the safety of the entire
$XYZ$.

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)=XYZ$, then without loss of generality we can assume
that a proper prefix of $W$ has $\textsc{end}(Y)Z$ as subwalk (the case where
a proper suffix of $W$ has $X\textsc{start}(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 $\textsc{end}(Y)Z$, in addition
to a solution walk that traverses $S$ one more time after traversing
$\textsc{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^{\prime}(e)=XYZ$ 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
$\textsc{end}(Y)Z$ and then exits $S$, as proven above. Therefore, $W$ is not
safe.∎

In the $\infty$-linear model, there exists a simple reduction from non-
strongly connected graphs to strongly connected graphs.

######  Theorem D.7 ($\infty$-st Safe Walks in General Graphs).

A walk is $\infty$-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 $\infty$-st safe in $G\cup\\{(t,s)\\}$, which is strongly connected.

###### Proof.

Since $G$ can be covered by a set of $s$-$t$ walks, it holds that
$G\cup\\{(t,s)\\}$ is strongly connected. For each set of solution walks in
$G$, a set of solution walks in $G\cup\\{(t,s)\\}$ can be constructed by
repeating one of the walks through $(t,s)$. Similarly, for each set of
solution walks in $G\cup\\{(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 $\infty$-st safe in $G$ if and only if it is $\infty$-st safe in
$G\cup\\{(t,s)\\}$. ∎

Using Theorem D.6, the $1$-st safe algorithm for strongly connected graphs
(see Theorem 7.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 checked in time linear in the length
of the safe walk in the SCC, resulting in a total runtime of
$O(m_{i}n_{i}+o_{i})$ where the SCC has $n_{i}$ nodes, $m_{i}$ arcs and the
total length of its safe walks is $o_{i}$. The overhead for finding the SCCs
and extending the inter-SCC arcs is $O(m+n)$ time, and solving the subproblems
including filtering subwalks takes an additional
$O((m_{1}n_{1}+o_{1})+(m_{2}n_{2}+o_{2})+\dots)$ time which is subset of
$O(mn+o)$ (where $o$ is the size of the output) since the $m_{i}$, $n_{i}$ and
$o_{i}$ add up to $m$, $n$ and $o$ respectively. For $\infty$-st safety by
Theorem D.7 we can use the $O(mn+o)$ algorithm for strongly connected graphs
in addition to linear preprocessing and postprocessing. Thus, we get the
following theorem.

######  Theorem D.8.

In a graph with $n$ nodes and $m$ arcs that admits a solution to the single
(or infinite) linear model, all maximal $1$-st safe (or $\infty$-st safe)
walks can be enumerated in $O(mn+o)$ time where $o$ is the size of the output.

######  Remark D.9.

For $k$ $s$-$t$ arc-covering walks where $1<k<\infty$, our characterisation
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.

###  D.2 Implementation

Note that the $k$-st safe problems are equivalent for all $k\geq 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 4.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 [8]. We compute
the hydrostructure for each non-trivial $\mathsf{Heart}(W)$ as well as each
trivial $W$, and check the conditions from Theorems 6.1 and 6.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 3.1 (a).

For each $W$, this algorithm performs safety checks linear in the length of
$W$. So since the total length of all maximal $1$-circular safe walks is
$O(mn)$ by Theorem 3.1 (b), at most $O(mn)$ walks need to be checked for
safety. A safety check includes building the hydrostructure in $O(m)$ time,
and checking the minimum walk-cover of the $\mathsf{River}$. The latter check
can be performed in $O(m)$ for $k=1$ since the check simplifies to checking if
the $\mathsf{River}$ is a path, and for $k\geq m$ the check is always false.
Otherwise, we use the $O(mn)$ flow algorithm mentioned in Section 3.

Additionally, the output size of this algorithm is limited. A trivial
avertible walk $W$ has maximal $k$-st safe subwalks of total length $O(|W|)$.
All other walks have length at most $O(n)$ each by Theorem 3.1 (b), and
therefore all maximal $k$-st safe subwalks of these have a total length of
$O(n^{2})$. Since the total length of trivial avertible walks is $O(mn)$, and
there are $O(n)$ other walks (by Theorem E.1), this results in an
$O(mn+n^{3})=O(n^{3})\leq O(m^{2}n)$ bound for the total length of maximal
$k$-st safe walks. Resulting, we get the following theorem.

######  Theorem D.10.

The problems $k$-st safe can be solved in $O(m^{2}n+mnf(m,n))$ time, or in
$O(m^{2}n)$ for $k=1$ or $k\geq m$.

###  D.3 Handling Trivial Avertible Walks in the Implementation

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 $E$-covering linear models. Consider that for a
trivial avertible walk $W^{l}WW^{r}$ where $W^{l}$ is its left wing, $W^{r}$
is its right wing and $W$ is its heart by Theorem E.3 (b) only subwalks of
$W^{l}W$ or $WW^{r}$ can be bridge-like. Therefore, the $k$-st safety of other
subwalks of $W^{l}WW^{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}WW^{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 $WW^{r}$, we describe only
$W^{l}W$ since the argument for $WW^{r}$ is symmetric. Consider that $W^{l}W$
is trivial, so by the conditions on the heart in the linear models (see
Theorem 6.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.11.

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 $WW^{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 6.1 (d) or
Theorem F.2 (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 D.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.12.

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.

##  Appendix E Omitted Hydrostructure Implementation Details

###  E.1 Basic Construction Algorithm

We prove the correctness of Theorem 4.5 using Algorithm 1.

Input: Graph $G$, non-empty walk $W$

Output: $R^{+}(W)$

1 if  _$W$ is an open path_ then

$R^{\prime}\leftarrow\\{x\in V\cup E\mid\exists\text{ $\textsc{start}(W)$-$x$
walk in }G\setminus\textsc{end}(W)\\}$

// compute e.g. via BFS

2 if  _$\not\exists\text{ arc }e\in R^{\prime}:e\notin
W\land\textsc{head}(e)\in W$_ then

3 return $R^{\prime}$

4

5

6return $G$

Algorithm 1 Forward Reachability

*

###### 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 Algorithm 1 and returns $G$. If $W$ is not an open
path, then by Lemma 4.3 this is correct. Otherwise, if $W$ is an open path,
there is an arc $e\in R^{\prime}$ such that $\textsc{tail}(e)\notin
W\land\textsc{head}(e)\in W\land e\neq\textsc{start}(W)$. Then, there is a
walk from $\textsc{start}(W)$ via $e$ to $\textsc{end}(W)$ that does not
contain $W$ as subwalk, so $W$ is avertible, and by Lemma 4.3 it follows that
outputting $G$ is correct, because $G=\mathsf{Vapor}(W)\subseteq
R^{+}(W)\subseteq G$.

  * •

Suppose Algorithm 1 reaches Algorithm 1 and returns $R^{\prime}$. Then for
that to be correct, by Lemma 4.3 $W$ must be bridge-like and $R^{\prime}$ must
be equal to $R^{+}(W)$.

Assume for a contradiction that $W$ is avertible. Then by Lemma 4.3 it holds
that $\mathsf{Vapor}(W)=G$, and therefore $R^{+}(W)=G$. Hence, by definition
of $R^{+}(\cdot)$, there is a $\textsc{start}(W)$-$\textsc{end}(W)$ walk
$\mathcal{W}$ that does not have $W$ as subwalk. Such a walk leaves $W$ before
reaching $\textsc{end}(W)$ to avoid having $W$ as subwalk. But then it must
enter $W$ again at an arc $e$ other than $\textsc{start}(W)$ before it reaches
$\textsc{end}(W)$ for the first time. Therefore, $e\in R^{\prime}$ and it
holds that $e\notin W$ and $\textsc{head}(e)\in W$. But then the condition in
Algorithm 1 would be false and Algorithm 1 would not reach Algorithm 1, a
contradiction.

Therefore, $W$ is bridge-like, and it remains to prove that
$R^{\prime}=R^{+}(W)$. $(\subseteq)$ Let $x\in R^{\prime}$. Then there is a
$\textsc{start}(W)$-$x$ walk in $G\setminus\textsc{end}(W)$, so $x\in
R^{+}(W)$. $(\supseteq)$ Let $x\in R^{+}(W)$. Then there is a
$\textsc{start}(W)$-$x$ walk in $G$ that does not contain $W$ as subwalk. This
walk cannot contain $\textsc{end}(W)$, since otherwise one of its prefixes
until $\textsc{end}(W)$ would prove $\textsc{end}(W)\in R^{+}(W)$,
contradicting Lemma 4.4 (c). So $x\in R^{\prime}$. ∎

###  E.2 Omitted Incremental Hydrostructure Proofs

*

###### Proof.

$(\subseteq)$ Let $x\in R^{+}(aZb)$. If $x\in aZ$, then it trivially holds, so
consider $x\notin aZ$. Then, since $aZb$ is bridge-like,
$x\in\mathsf{Sea}(aZb)$. So by Lemma 4.4 (d), there is an $a$-$x$ path $P$ in
$\mathsf{Sea}(aZb)\cup\mathsf{Vapor}(aZb)$. Let $v$ be the last element of $P$
in $\mathsf{Vapor}(aZb)$; it exists since
$\textsc{head}(a)\in\mathsf{Vapor}(aZb)$, and since $\mathsf{Vapor}(aZb)$ is a
path by Lemma 4.3, $v$ is a node.Let $e^{\prime}$ be the outgoing arc of $v$
in $P$ and $e$ its sibling in $Zb$; notice that $e^{\prime}\neq b$, since
$b\in\mathsf{Cloud}(aZb)$. By definition of $R_{sib}^{+}(\cdot)$, it holds
that the suffix of $P$ starting from $e^{\prime}$ is in $R_{sib}^{+}(e)$ and,
as such, $x\in R_{sib}^{+}(e)$.

$(\supseteq)$ By definition, $aZ\subseteq R^{+}(aZb)$. Let $x\in
R_{sib}^{+}(e)$, for some arc $e$ from $Zb$. Since $aZb$ is bridge-like, by
Lemma 4.3, $Z$ is an open path, and therefore $aZ$ is a path. As a result,
there is a path $P$ from $a$ to $\textsc{tail}(e)$ via a prefix of $Z$ that
does not contain $e$. Since $x\in R_{sib}^{+}(e)$, $P$ can be extended to $x$
without using $e$. So there is a walk from $a$ to $x$ without using $e\in Zb$,
so $x\in R^{+}(aZb)$. ∎

*

###### Proof.

  * (a)

Let $x\in R_{sib}^{+}(e)$. Then by Lemma 7.1, $x\in R^{+}(aZb)$, so there is a
walk from $a$ to $x$ which, by Lemma 4.4 (c), does not include $b$. Moreover,
by Lemma 4.4 (d), there is a walk from each split-sibling of $b$ to $a$ that
does not include $b$. So $x\in R_{sib}^{+}(b)$.

  * (b)

$(\subseteq)$ Assume for a contradiction, that $x\in R_{sib}^{+}(b)$ but not
in $R_{sib}^{+}(e)\cup\\{x\in G\mid\exists\text{ $e$-$x$ walk in
}G\setminus(R_{sib}^{+}(e)\cup\\{b\\})\\}$. Since $x\in R_{sib}^{+}(b)$, there
is a $\textsc{tail}(b)$-$x$ walk $W$ in $G\setminus\\{b\\}$. Moreover, since
by Lemma 4.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^{\prime}$ in
$G\setminus\\{b\\}$. Since $x\notin R_{sib}^{+}(e)$ and $W^{\prime}$ starts in
$e$, $W^{\prime}$ must contain a suffix starting in some occurrence of $e$
that contains no elements of $R_{sib}^{+}(e)$. But then that suffix of
$W^{\prime}$ is an $e$-$x$ walk in $G\setminus(R_{sib}^{+}(e)\cup\\{b\\})$, a
contradiction.

$(\supseteq)$ If $x\in R_{sib}^{+}(e)$ then $x\in R_{sib}^{+}(b)$ by Lemma 7.2
(a). Otherwise there is an $e$-$x$ walk in
$G\setminus(R_{sib}^{+}(e)\cup\\{b\\})\\}$. Since $aZb$ is bridge-like, it
holds that each split sibling of $b$ is in $\mathsf{Sea}(aZb)$. By Lemma 4.4
(d) there is a walk from each split sibling of $b$ to $e$ in
$\mathsf{Sea}(aZb)\cup Z$. Notice that by Lemma 4.4 (c),
$b\in\mathsf{Cloud}(aZb)$, so these walks do not contain $b$ since $Z$ is
$\mathsf{Vapor}(aZb)$. So there exists an $\textsc{tail}(b)$-$x$ walk via $e$
in $G\setminus\\{b\\}$, so $x\in R_{sib}^{+}(b)$. ∎

###  E.3 Supporting Theorems for the Incremental Algorithms

######  Theorem E.1.

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\in 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\in\mathsf{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 [25], 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 3.1 (b). ∎

######  Lemma E.2 (restate = italianopath, name = ).

Let $W$ be a trivial $a$-$b$ walk in a strongly connected graph with $n$ nodes
and $m$ arcs and let $e\in\mathsf{Heart}(W)$ be an arc with
$e\notin\\{a,b\\}$. After $O(m)$ time preprocessing, the query _“is there an
$a$-$b$ path in $G\setminus e$”_ can be answered in $O(1)$-time.

###### Proof.