The BEST theorem — named for de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte — counts the number of Eulerian trails in a directed graph as a product involving the number of arborescences and the out-degrees. Counting is elegant. But enumerating — listing all the trails one by one — has historically gone through the count: first enumerate arborescences, then convert each to an Eulerian trail via the bijection implicit in the BEST theorem.
Bals, Pissis, and Tinca bypass the theorem entirely. Their algorithm directly enumerates all z_T Eulerian trails in O(m + z_T) time — linear in the graph size plus the output size. This is optimal: you can't do better than reading the graph once and writing each trail once.
The algorithm is described as “remarkably simple.” It maintains a partially constructed trail and backtracks when stuck, using the graph's edge structure to guide the search without revisiting dead ends. The simplicity is the point — the BEST theorem's elegant counting formula suggests that the combinatorial structure of Eulerian trails is deeply connected to spanning arborescences. But for enumeration, that connection is a detour. Going through arborescences adds a multiplicative factor to the running time that the direct approach avoids.
The structural observation: the best way to count something and the best way to list it can use completely different mathematics. The BEST theorem is beautiful for counting — it reduces a graph-traversal problem to a determinantal formula. But for enumeration, the formula is overhead. The direct algorithm works because traversal is a local operation, and enumerating local choices is cheaper than computing a global algebraic invariant for each one.