Beyond the BEST Theorem: Fast Assessment of Eulerian Trails - Archive ouverte HAL Access content directly
Conference Papers Year :

## Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

(1) , (2, 1) , (3) , (2, 1) , (4, 5, 2, 1) , (1)
1
2
3
4
5
Alessio Conte
• Function : Author
• PersonId : 991829
Roberto Grossi
• Function : Author
• PersonId : 857937
Grigorios Loukides
• Function : Author
• PersonId : 1033574
• Function : Author
• PersonId : 843474
Giulia Punzi
• Function : Author
• PersonId : 1057110

#### Abstract

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.

#### Domains

Computer Science [cs]

### Dates and versions

hal-03498416 , version 1 (21-12-2021)

### Identifiers

• HAL Id : hal-03498416 , version 1
• DOI :

### Cite

Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon Pissis, et al.. Beyond the BEST Theorem: Fast Assessment of Eulerian Trails. FCT 2021 - 23rd International Symposium on Fundamentals of Computation Theory, Sep 2021, Athens, Greece. pp.162-175, ⟨10.1007/978-3-030-86593-1_11⟩. ⟨hal-03498416⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

12 View