2021-09-09

# Beyond the BEST Theorem: Fast assessment of Eulerian Trails

## Publication

### Publication

*Presented at the FCT 2021: Fundamentals of Computation Theory (September 2021), Athens, Greece*

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 O(nω) arithmetic operations by applying the well-known BEST theorem, where ω< 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) ≥ 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 O(m· min { z, # ET(G) }) time.

Additional Metadata | |
---|---|

ERABLE team, Lyon, France | |

doi.org/10.1007/978-3-030-86593-1_11 | |

Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |

Pan-genome Graph Algorithms and Data Integration , Algorithms for PAngenome Computational Analysis | |

FCT 2021: Fundamentals of Computation Theory | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |

Conte, A, Grossi, R, Loukides, G, Pisanti, N, Pissis, S, & Punzi, G. (2021). Beyond the BEST Theorem: Fast assessment of Eulerian Trails. In
Proceedings of Fundamentals of Computation Theory (pp. 162–175). doi:10.1007/978-3-030-86593-1_11 |