Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

Given 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 \(\mathcal {O}(n^{\omega })\) arithmetic operations by applying the well-known BEST theorem, where \(\omega <2.373\) denotes the matrix multiplication exponent. The algorithmic challenge is: Can we solve this problem faster for certain values of m and z? Namely, we want to design a combinatorial algorithm for assessing whether \(\#ET(G) \ge z\), which does not resort to the BEST theorem and has a predictably bounded cost as a function of m and z. We address this challenge here by providing a combinatorial algorithm requiring \(\mathcal {O}(m\cdot \min \{z, \#ET(G)\})\) time.