## 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.

Original language | English |
---|---|

Title of host publication | Fundamentals of Computation Theory |

Subtitle of host publication | 23rd International Symposium, FCT 2021, Athens, Greece, September 12–15, 2021, Proceedings |

Editors | Evripidis Bampis, Aris Pagourtzis |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 162-175 |

Number of pages | 14 |

ISBN (Electronic) | 9783030865931 |

ISBN (Print) | 9783030865924 |

DOIs | |

Publication status | Published - 2021 |

Event | 23rd International Symposium on Fundamentals of Computation Theory, FCT 2021 - Virtual, Online Duration: 12 Sept 2021 → 15 Sept 2021 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 12867 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 23rd International Symposium on Fundamentals of Computation Theory, FCT 2021 |
---|---|

City | Virtual, Online |

Period | 12/09/21 → 15/09/21 |

### Bibliographical note

Funding Information:Acknowledgments. We wish to thank Luca Versari for useful discussions on a previous version of the main algorithm. This paper is part of the PANGAIA project that has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 872539. This paper is also part of the ALPACA project that has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 956229.

Publisher Copyright:

© 2021, Springer Nature Switzerland AG.