Shortest Undirected Paths in de Bruijn Graphs

Wiktor Zuba; Oded Lachish; Solon P. Pissis

doi:10.4230/LIPIcs.CPM.2025.12

Shortest Undirected Paths in de Bruijn Graphs

Wiktor Zuba
, Oded Lachish
, Solon P. Pissis

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Computing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V, E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from O(k|V |²) to O(k|V |log d) time, where d is the number of weakly connected components of graph G.

Original language	English
Title of host publication	36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)
Subtitle of host publication	[Proceedings]
Editors	Paola Bonizzoni, Veli Makinen
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	1-13
Number of pages	13
ISBN (Electronic)	9783959773690
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2025.12
Publication status	Published - 2025
Event	36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025 - Milan, Italy Duration: 17 Jun 2025 → 19 Jun 2025

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	331
ISSN (Print)	1868-8969

Conference

Conference	36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025
Country/Territory	Italy
City	Milan
Period	17/06/25 → 19/06/25

Bibliographical note

Publisher Copyright:
© Wiktor Zuba, Oded Lachish, and Solon P. Pissis;

Keywords

de Bruijn graph
Eulerian graph
graph algorithm
string algorithm

Access to Document

10.4230/LIPIcs.CPM.2025.12Licence: CC BY

Persistent URL (handle)

Persistent link

Cite this

Zuba, W., Lachish, O., & Pissis, S. P. (2025). Shortest Undirected Paths in de Bruijn Graphs. In P. Bonizzoni, & V. Makinen (Eds.), 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025): [Proceedings] (pp. 1-13). Article 12 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 331). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CPM.2025.12

Zuba, Wiktor ; Lachish, Oded ; Pissis, Solon P. / Shortest Undirected Paths in de Bruijn Graphs. 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025): [Proceedings]. editor / Paola Bonizzoni ; Veli Makinen. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. pp. 1-13 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{fe7c74be39b34e1eb2f88c6854c7c428,

title = "Shortest Undirected Paths in de Bruijn Graphs",

abstract = "Computing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V, E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from O(k|V |2) to O(k|V |log d) time, where d is the number of weakly connected components of graph G.",

keywords = "de Bruijn graph, Eulerian graph, graph algorithm, string algorithm",

author = "Wiktor Zuba and Oded Lachish and Pissis, \{Solon P.\}",

note = "Publisher Copyright: {\textcopyright} Wiktor Zuba, Oded Lachish, and Solon P. Pissis;; 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025 ; Conference date: 17-06-2025 Through 19-06-2025",

year = "2025",

doi = "10.4230/LIPIcs.CPM.2025.12",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "1--13",

editor = "Paola Bonizzoni and Veli Makinen",

booktitle = "36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)",

}

Zuba, W, Lachish, O & Pissis, SP 2025, Shortest Undirected Paths in de Bruijn Graphs. in P Bonizzoni & V Makinen (eds), 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025): [Proceedings]., 12, Leibniz International Proceedings in Informatics, LIPIcs, vol. 331, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 1-13, 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, Milan, Italy, 17/06/25. https://doi.org/10.4230/LIPIcs.CPM.2025.12

Shortest Undirected Paths in de Bruijn Graphs. / Zuba, Wiktor; Lachish, Oded; Pissis, Solon P.
36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025): [Proceedings]. ed. / Paola Bonizzoni; Veli Makinen. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. p. 1-13 12 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 331).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Shortest Undirected Paths in de Bruijn Graphs

AU - Zuba, Wiktor

AU - Lachish, Oded

AU - Pissis, Solon P.

N1 - Publisher Copyright: © Wiktor Zuba, Oded Lachish, and Solon P. Pissis;

PY - 2025

Y1 - 2025

N2 - Computing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V, E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from O(k|V |2) to O(k|V |log d) time, where d is the number of weakly connected components of graph G.

AB - Computing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V, E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from O(k|V |2) to O(k|V |log d) time, where d is the number of weakly connected components of graph G.

KW - de Bruijn graph

KW - Eulerian graph

KW - graph algorithm

KW - string algorithm

UR - https://www.scopus.com/pages/publications/105008312285

UR - https://www.scopus.com/pages/publications/105008312285#tab=citedBy

UR - https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-331

U2 - 10.4230/LIPIcs.CPM.2025.12

DO - 10.4230/LIPIcs.CPM.2025.12

M3 - Conference contribution

AN - SCOPUS:105008312285

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 13

BT - 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

A2 - Bonizzoni, Paola

A2 - Makinen, Veli

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025

Y2 - 17 June 2025 through 19 June 2025

ER -

Zuba W, Lachish O, Pissis SP. Shortest Undirected Paths in de Bruijn Graphs. In Bonizzoni P, Makinen V, editors, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025): [Proceedings]. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2025. p. 1-13. 12. (Leibniz International Proceedings in Informatics, LIPIcs). Epub 2025 Jun 10. doi: 10.4230/LIPIcs.CPM.2025.12

Shortest Undirected Paths in de Bruijn Graphs

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this