Shortest Undirected Paths in de Bruijn Graphs

is not the case for computing undirected paths, which is algorithmically much more challenging. 13 Here we present a general framework for computing shortest undirected paths in arbitrary de Bruijn 14 graphs. We then present an application of our techniques for making any arbitrary order-k de Bruijn 15 graph G(V,E) weakly connected by adding a set of edges of minimal total cost. This improves on 16 the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] 17 from O(k|V |2) to O(k|V | log d) time, where d is the number of weakly connected components of G.