Shortest Undirected Paths in de Bruijn Graphs

Bernardini et al. [4] studied the problem of making any arbitrary $G_{𝒮,k}$ weakly connected by introducing a set of new edges of minimum total cost (as well as the underlying set of new nodes when those do not exist in $G_{𝒮,k}$); by arbitrary $G_{𝒮,k}$, we mean an arbitrary subgraph of the complete dBG $G_{\mathrm{\Sigma },k}$. Note that making any arbitrary graph weakly connected by introducing a set of new edges of minimum total cost is trivial: if the graph consists of $d$ components, the solution is to greedily add $d-1$ edges to connect the components. The algorithmic challenge with dBGs follows by their definition: not every pair of nodes can be connected via a single edge. Solving this problem is important because we can then use the linear-time algorithm of Bernardini et al. from [5] to balance the weakly connected graph by adding a set of edges of minimum total cost thus making $G_{𝒮,k}$ Eulerian.¹¹1By Euler’s famous theorem, we know that a weakly connected directed graph is Eulerian if and only if every graph node has equal in-degree and out-degree (except perhaps for the source and target). Recall that making $G_{𝒮,k}$ directly Eulerian by adding a set of new edges of minimum total cost is NP-hard from the well-known shortest common superstring problem [12]; hence, the connect-and-balance strategy is reasonable and generally serves as a good-performing heuristic [5]. Two remarks are in order: first, since the general task is to connect $G_{𝒮,k}$, we can safely assume that $m_{u,v}$ is either $0$ or $1$ (i.e., multiplicities play no role here); and second, since the task, in particular, is to connect $G_{𝒮,k}$ with the smallest number of edge additions, we should rather seek shortest undirected paths in $G_{𝒮,k}$ (i.e., shortest sequences of edges from $G_{\mathrm{\Sigma },k}$, in which the edge directions are neglected). Inspect Figure 2.

Bernardini et al. [4] showed that making $G_{𝒮,k}$ weakly connected by adding a set of edges of minimum total cost is NP-hard. They also showed that no polynomial-time approximation scheme (PTAS) exists for making $G_{𝒮,k}$ weakly connected by adding a set of edges of minimum total cost (unless the unique games conjecture [13] fails). Finally, they also showed that there exists an $𝒪(k{|V|}^2)$-time $(2-2/d)$-approximation algorithm for the same problem, where $d$ is the number of connected components of $G_{𝒮,k}$. In this paper, we introduce a general framework for finding shortest undirected paths in dBGs. In particular, using our framework, we improve the running time of the approximation algorithm of Bernardini et al. from $𝒪(k{|V|}^2)$ to $𝒪(k|V|\log d)$, while maintaining the same approximation ratio.

Let us fix $d$ families $C_1,C_2,\mathrm{\dots },C_d$ of nodes (forming connected components in most applications) from $G_{\mathrm{\Sigma },k}$, and let us denote $V=C_1\bigsqcup C_2\bigsqcup \mathrm{\cdots }\bigsqcup C_d$.²²2We assume that these families are pairwise disjoint. However, our solutions work without this assumption. Throughout this paper, we treat nodes of dBGs and their length-$k$ string representations as equivalent: indeed, nodes of $G_{\mathrm{\Sigma },k}$ are in a natural bijection with ${\mathrm{\Sigma }}^k$. In particular, $C_p$, for any $p\in [1,d]$, and $V$ are also treated as sets of strings.

We generally aim at obtaining efficient algorithms for finding the minimal distance between the nodes from two different families $C_p$ and $C_q$; more formally, for any $p,q\in [1,d]$,

where $\text{dist}(u,v)$ is the length of a shortest undirected path from node $u$ to node $v$ in $G_{\mathrm{\Sigma },k}$.

Note that if $C_p$ and $C_q$ form two weakly connected components of $G_{\mathrm{\Sigma },k}$, then $\text{dist}(p,q)$ is precisely the minimum number of edges that must be added to connect the two components into a single one – assuming that we also add the nodes implied by those edges. In the same manner, by adding $d-1$ such undirected paths, we can (greedily) connect $C_1,C_2,\mathrm{\dots },C_d$ to a single component, thus making any arbitrary dBG $G_{𝒮,k}$ weakly connected.

The problem of finding the shortest directed path between any two nodes of $G_{\mathrm{\Sigma },k}$ can be solved in the optimal $𝒪(k)$ time using the preprocessing of the classic KMP algorithm [14]. The same problem for undirected paths can also be solved in the optimal $𝒪(k)$ time [16]. By iteratively applying the latter result, we can compute $\text{dist}(p,q)$ in $𝒪(k|C_p|\cdot |C_q|)$ time and for all $p,q$ pairs in $𝒪(k{|V|}^2)$ total time, which is very slow when $|V|$ is large, even if the number $d$ of families is relatively small. Using more refined techniques, based on the generalized suffix tree [25] of the strings from $V$, we develop algorithms for finding the distances much more efficiently when the families are large or when there are many of them.

In particular, given the collection $C_1,C_2,\mathrm{\dots },C_d$, we consider the following problems:

• $\mathrm{■}$

  $\text{One-to-One}(p,q)$: output $\text{dist}(p,q)$. Here we are given, in addition, $p$ and $q$, and we are asked to find the length of a shortest undirected path between any node of $C_p$ and any node of $C_q$.

• $\mathrm{■}$

  $\text{One-to-All}(p)$: output $\text{dist}(p,q)$, for every $q\in [1,d]$. Here we are given, in addition, $p$, and we are asked to find the length of a shortest undirected path between any node of $C_p$ and any node of $C_q$, for every $q\in [1,d]$.

• $\mathrm{■}$

  All-to-All: output $\text{dist}(p,q)$, for all $p,q\in [1,d]$. Here we are asked to find the length of a shortest undirected path between any node of $C_p$ and any node of $C_q$, for all $p,q\in [1,d]$.

• $\mathrm{■}$

  $\text{Top}(r)$: Here we are given, in addition, $r$, and we are asked to output, for every $q\in [1,d]$, $r$ distinct $p\in [1,d]$ with the smallest value of $\text{dist}(p,q)$, breaking ties arbitrarily.

Let us remark that the algorithms underlying our framework are constructive – whenever we compute $\text{dist}(p,q)$, we also know a pair $u\in C_p,v\in C_q$ of nodes that are at distance $\text{dist}(p,q)$. By applying the technique from [16], we can enhance the output of the above algorithms with optimal paths realising those distances at the additional linear cost in the size of the output – $k$ times the length of a shortest path (every node is explicitly encoded using $k$ letters). If the output is given in a compacted form – the differences between two consecutive nodes on the path (the new letter introduced and whether it is put in the front or back) – then the additional cost reduces to the length of the shortest path.

We make the following specific contributions:

• $\mathrm{■}$

  an algorithm solving $\text{One-to-One}(p,q)$ in $𝒪(k(|C_p|+|C_q|))$ time and space;

• $\mathrm{■}$

  an algorithm solving $\text{One-to-All}(p)$ in $𝒪(k|V|)$ time and space;

• $\mathrm{■}$

  an algorithm solving All-to-All in $𝒪(dk|V|)$ time and $𝒪(k|V|)$ space;

• $\mathrm{■}$

  an algorithm solving $\text{Top}(r)$ in $𝒪(rk|V|)$ time and space.

By plugging our results directly in the approximation algorithm of Bernardini et al. [4], we improve the running time of their algorithm for connecting dBGs from $𝒪(k{|V|}^2)$ to $𝒪(dk|V|)$. Using more refined techniques, we obtain an even further improvement; in particular, we design an $𝒪(k|V|\log d)$-time algorithm for the same task, while maintaining the same approximation ratio of $(2-2/d)$ [4].

In Section 2, we present some preliminaries that essentially summarize the work in [16]. In Section 3, we present a simple linear-time algorithm for computing shortest paths in undirected dBGs. In Section 4, we present our framework: how distances between sets of nodes can be computed more efficiently in many settings. In Section 5, we apply our framework to the problem of making any arbitrary dBG weakly connected [4].

The classic indexing solution for standard strings is the suffix tree [25]. Given a set $ℱ$ of strings, the compacted trie of these strings is the trie obtained by compressing each path of nodes of degree one in the trie of the strings in $ℱ$. The dissolved nodes are called implicit while the preserved nodes are called explicit. For any node $u$ (implicit of explicit) of the compacted trie, $\text{str}(u)$ denotes the string spelled from the root of the trie to $u$; the string depth of $u$ is then defined as $d(u)=|\text{str}(u)|$. Each edge in the compacted trie has a label represented as a fragment of a string in $ℱ$. Thus, the compacted trie uses $𝒪(|ℱ|)$ space [20]. The suffix tree $\text{ST}(S)$ is the compacted trie of the suffixes of string $S$. Assuming $S$ ends with a unique terminating symbol $\$$, every suffix $S[i..|S|)$ of $S$ is represented by a leaf annotated with index $i$ (the starting position of the suffix in $S$). The root node, the branching nodes, and the leaf nodes form the set of explicit nodes of $\text{ST}(S)$; inspect Figure 4. The suffix tree occupies $𝒪(|S|)$ space and it can be constructed in $𝒪(|S|)$ time [25, 11]. The edges of $\text{ST}(S)$ can be accessed in $𝒪(1)$ time if stored using perfect hashing [2]. The suffix tree then supports pattern matching queries for any pattern $P$ of length $m$ in $𝒪(m+|\text{Occ}|)$ time, where Occ is the set of output occurrences of $P$ in $S$. The suffix tree can also be generalized to a collection $𝒮=\{S_1,\mathrm{\dots },S_N\}$ of $N$ strings as the compacted trie $\text{ST}(𝒮)$ of the suffixes of string $S_1{\$}_1\mathrm{\cdots }{S}_N{\$}_N$, where ${\$}_i\notin \mathrm{\Sigma }$, for $i\in [1,N]$, are distinct terminating symbols.

We show that starting from any arbitrary spanning tree of $𝒢$, we can modify it using a greedy approach so that the obtained spanning tree contains all edges of $E_{\text{Top}}$, and has a total weight at most as large as the weight of the initial spanning tree.

We iterate over the edges of $E_{\text{Top}}$; we add the edge to the spanning tree and then remove one edge from the newly created cycle: the one with the largest weight and, among possibly many such edges, we prefer an edge that does not belong to $E_{\text{Top}}$.

Clearly, such an operation cannot increase the weight of the spanning tree – the worst-case scenario is that the newly added edge is immediately removed. If by applying this procedure, we never remove any edge from $E_{\text{Top}}$, then the claimed solution exists.

Towards the contradiction assume that after adding an edge $e_1\in E_{\text{Top}}$, we create a cycle in which all the heaviest edges belong to $E_{\text{Top}}$. Take one such edge – it was chosen for a node $v$. The other edge of the cycle incident with $v$ cannot be lighter (by the definition of $E_{\text{Top}}$), hence by assumption it must have the same weight and hence must also belong to $E_{\text{Top}}$ (by the assumption of this paragraph of the proof); we move on to the node for which this edge was chosen, and continue in the same way. Since the cycle is finite, at some point we have to come back to $v$ – but this means that the edges from $E_{\text{Top}}$ formed a cycle – a contradiction with the definition of $E_{\text{Top}}$. Thus, $E_{\text{Top}}$ is a subset of a minimum spanning tree of $𝒢(𝒱,ℰ)$. $◀$

Recall that $G^{\prime }(V^{\prime },E^{\prime })$ is the graph obtained from the complete dBG $G_{\mathrm{\Sigma },k}$ by collapsing each component $C_p$, $p\in [1,d]$, of $G(V,E)$ into one super-node. We show the following lemma (implementing the algorithm of [8]).

Let us remark that we do not explicitly construct $G^{\prime }$ or $G_{\mathrm{\Sigma },k}$.

We start by producing a set of edges $E_{\text{Top}}$ for $G^{\prime }$ using a $\text{Top}(r)$ query for $r=2$. Such a query returns for each component $C_q$ of $G$, that is, equivalently for each super-node $q$ of $G^{\prime }$, two super-nodes closest to it. In particular, what is implied by this is that even if one of those two is $q$ itself (which happens in most cases), the other one must be different. By Theorem 9, in $𝒪(k|V|)$ total time, we find, for each super-node of $G^{\prime }$, one incident edge with the smallest weight possible – by taking this set of edges and removing from each cycle a single edge we obtain a valid set of edges $E_{\text{Top}}$.

By Lemma 11, we can safely report this set of edges as part of the output. We can also contract the super-nodes of $G^{\prime }$ connected with the edges from $E_{\text{Top}}$ into other single super-nodes obtaining graph $G^{\prime \prime }$. Now every spanning tree of $G^{\prime }$ that contains $E_{\text{Top}}$ is equivalent to the union of a spanning tree of $G^{\prime \prime }$ and the set $E_{\text{Top}}$, hence the problem reduces to finding the minimum spanning tree of $G^{\prime \prime }$.

Notice that $G^{\prime \prime }$ is represented by the very same input to our original problem on a dBG, just with some of the sets $C_p$ merged together, and so we can use the same generalized suffix tree just with different labels $p,q$. We can thus repeat the same approach until we reach a graph with a single super-node. Note that each such iteration takes $𝒪(k|V|)$ time (Theorem 9), and that there can be no more than ${\log }_{2}d$ such iterations because each time every super-node gets connected to another one, the number of super-nodes (components) drop by at least the factor $2$ – the statement follows. $◀$

By applying Lemma 12 to the solution from [4] we obtain the following improved result.

Since the algorithm underlying Theorem 13 is near-optimal, the main open question is whether we can improve the approximation ratio.