Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giulia Punzi*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationFundamentals of Computation Theory
Subtitle of host publication23rd International Symposium, FCT 2021, Athens, Greece, September 12–15, 2021, Proceedings
EditorsEvripidis Bampis, Aris Pagourtzis
PublisherSpringer Science and Business Media Deutschland GmbH
Pages162-175
Number of pages14
ISBN (Electronic)9783030865931
ISBN (Print)9783030865924
DOIs
Publication statusPublished - 2021
Event23rd International Symposium on Fundamentals of Computation Theory, FCT 2021 - Virtual, Online
Duration: 12 Sep 202115 Sep 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12867 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Symposium on Fundamentals of Computation Theory, FCT 2021
CityVirtual, Online
Period12/09/2115/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.

Fingerprint

Dive into the research topics of 'Beyond the BEST Theorem: Fast Assessment of Eulerian Trails'. Together they form a unique fingerprint.

Cite this