Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

International audienceGiven a directed multigraph $G=(V,E)$ , with $|V|=n$ nodes and $|E|=m$ edges, and an integer $z$, we are asked to assess whether the number #$ET$($G$) of node-distinct Eulerian trails of $G$ is at least $z$; two trails are called node-distinct if their node sequences are different. This problem has been formalized by Bernardini et al. [ALENEX 2020] as it is the core computational problem in several string processing applications. It can be solved in $O$($nω$) arithmetic operations by applying the well-known BEST theorem, where $ω