2026-08-25T18:47:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27196 2026-08-25T13:18:17Z ddc:004 open_access

Optimal Enumeration of Eulerian Trails in Directed Graphs Bals, Ben Pissis, Solon P. Tinca, Matei graph algorithms enumeration algorithms Eulerian trails Eulerian paths The BEST theorem, due to de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, is a classical tool from graph theory that links the Eulerian trails in a directed graph G = (V,E) with the arborescences in G. In particular, one can use the BEST theorem to count the Eulerian trails in G in polynomial time. For enumerating the Eulerian trails in G, one could naturally resort to first enumerating the arborescences in G and then exploiting the insight of the BEST theorem to enumerate the Eulerian trails in G: every arborescence in G corresponds to at least one Eulerian trail in G. For over two decades, the fastest algorithm for enumerating arborescences in G took 𝒪(m log n + n + z_A log²n) time, where n = |V|, m = |E|, and z_A is the number of arborescences in G [Uno, ISAAC 1998]. Since Uno’s algorithm does not lead to an optimal enumeration of Eulerian trails in directed graphs, we were motivated to develop a direct algorithm for this problem. Our central contribution is a remarkably simple algorithm to directly enumerate the z_T Eulerian trails in G in the optimal 𝒪(m + z_T) time. As a consequence, our result improves on an implementation of the BEST theorem for counting Eulerian trails in G when z_T = o(n²), and also unconditionally improves the combinatorial 𝒪(m⋅z_T)-time algorithm of Conte et al. [TKDD 2026] for the same task. Moreover, we show that, with some care, our algorithm can be extended to enumerate Eulerian trails in directed multigraphs in optimal time, enabling applications in bioinformatics and data privacy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ben Bals and Solon P. Pissis and Matei Tinca 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.60 urn:nbn:de:0030-drops-271960 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.60 eng https://creativecommons.org/licenses/by/4.0/legalcode