Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

Alessio Conte; Roberto Grossi; Grigorios Loukidis; Nadia Pisanti; Solon  Pissis; Giulia Punzi

Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

Alessio Conte, Roberto Grossi, Grigorios Loukidis, Nadia Pisanti, Solon Pissis, Giulia Punzi

Research output: Contribution to journal › Article › peer-review

87 Downloads (Pure)

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(n⋅min{z,#ET(G)}) time.

Original language	English
Journal	Fundamentals of Computation Theory
Publication status	Accepted/In press - 29 Jun 2021

Access to Document

Estimating_Eulerian_Trails_FCTAccepted author manuscript, 368 KB

Cite this

@article{c477c2b2458f47de981835dd52fa3dfe,

title = "Beyond the BEST Theorem: Fast Assessment of Eulerian Trails",

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(n⋅min{z,#ET(G)}) time.",

author = "Alessio Conte and Roberto Grossi and Grigorios Loukidis and Nadia Pisanti and Solon Pissis and Giulia Punzi",

year = "2021",

month = jun,

day = "29",

language = "English",

journal = "Fundamentals of Computation Theory",

issn = "0302-9743",

publisher = "Springer",

}

TY - JOUR

T1 - Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

AU - Conte, Alessio

AU - Grossi, Roberto

AU - Loukidis, Grigorios

AU - Pisanti, Nadia

AU - Pissis, Solon

AU - Punzi, Giulia

PY - 2021/6/29

Y1 - 2021/6/29

N2 - 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(n⋅min{z,#ET(G)}) time.

AB - 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(n⋅min{z,#ET(G)}) time.

M3 - Article

SN - 0302-9743

JO - Fundamentals of Computation Theory

JF - Fundamentals of Computation Theory

ER -

Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

Abstract

Access to Document

Fingerprint

Cite this