Research output: Other contribution

**Fast Assessment of Eulerian Trails.** / Conte, Alessio; Grossi, Roberto; Loukidis, Grigorios; Pisanti, Nadia; Pissis, Solon ; Punzi, Giulia.

Research output: Other contribution

Conte, A, Grossi, R, Loukidis, G, Pisanti, N, Pissis, S & Punzi, G 2020, *Fast Assessment of Eulerian Trails*..

Conte, A., Grossi, R., Loukidis, G., Pisanti, N., Pissis, S., & Punzi, G. (2020, Oct 26). Fast Assessment of Eulerian Trails. Unpublished.

Conte A, Grossi R, Loukidis G, Pisanti N, Pissis S, Punzi G. Fast Assessment of Eulerian Trails. 2020.

@misc{2a90244fef374a26b9266d7437b0f208,

title = "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 {\em node-distinct} if their node sequences are different. This problem has been very recently posed by Bernardini et al.~[ALENEX 2020]. It can be solved in $O(n^{\omega})$ arithmetic operations by applying the well-known BEST theorem, where $\omega<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 $\#ET(G) \geq z$ that does not resort to the BEST theorem and has a cost that is predictably bounded as a function of $m$ and $z$. We address this challenge by providing an algorithm requiring $O(m\cdot \min\{z, \#ET(G)\})$ time. This gives a time-optimal algorithm for $z=O(1)$ or for $\#ET(G)=O(1)$. The impact of this theoretical result on real-world graphs is striking: a simple implementation of our algorithm takes tens of seconds to assess $\#ET(G) \geq z$, whereas a highly-optimized implementation of the BEST theorem requires more than 12 hours. The most surprising consequence of our techniques for directed graphs is that they extend straightforwardly to undirected graphs, for which the underlying counting problem is \#P-complete [Brightwell and Winkler, ALENEX/ANALCO 2005]: we provide an algorithm for assessing $\#ET(G) \geq z$ in an undirected multigraph $G$ requiring time polynomial in $m$ and in $z$. Bernardini et al.~reduced the following problem on strings to the aforementioned assessment problem for directed graphs: Given a string $T$ and an integer $z$, find the largest $d$ such that there exist at least $z$ strings having the same multiplicities of length-$d$ substrings as $T$. The authors proposed an $\cO(|T|^{\omega} \log d)$-time algorithm to solve this problem by applying the BEST theorem to compute the largest $d$ for which $\#ET(G)\geq z$, where $G$ is the order-$d$ de Bruijn graph of $T$. Our algorithm for directed graphs can directly solve the same problem in $O(|T|z \log d)$ time. ",

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

year = "2020",

month = oct,

day = "26",

language = "English",

type = "Other",

}

TY - GEN

T1 - Fast Assessment of Eulerian Trails

AU - Conte, Alessio

AU - Grossi, Roberto

AU - Loukidis, Grigorios

AU - Pisanti, Nadia

AU - Pissis, Solon

AU - Punzi, Giulia

PY - 2020/10/26

Y1 - 2020/10/26

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 {\em node-distinct} if their node sequences are different. This problem has been very recently posed by Bernardini et al.~[ALENEX 2020]. It can be solved in $O(n^{\omega})$ arithmetic operations by applying the well-known BEST theorem, where $\omega<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 $\#ET(G) \geq z$ that does not resort to the BEST theorem and has a cost that is predictably bounded as a function of $m$ and $z$. We address this challenge by providing an algorithm requiring $O(m\cdot \min\{z, \#ET(G)\})$ time. This gives a time-optimal algorithm for $z=O(1)$ or for $\#ET(G)=O(1)$. The impact of this theoretical result on real-world graphs is striking: a simple implementation of our algorithm takes tens of seconds to assess $\#ET(G) \geq z$, whereas a highly-optimized implementation of the BEST theorem requires more than 12 hours. The most surprising consequence of our techniques for directed graphs is that they extend straightforwardly to undirected graphs, for which the underlying counting problem is \#P-complete [Brightwell and Winkler, ALENEX/ANALCO 2005]: we provide an algorithm for assessing $\#ET(G) \geq z$ in an undirected multigraph $G$ requiring time polynomial in $m$ and in $z$. Bernardini et al.~reduced the following problem on strings to the aforementioned assessment problem for directed graphs: Given a string $T$ and an integer $z$, find the largest $d$ such that there exist at least $z$ strings having the same multiplicities of length-$d$ substrings as $T$. The authors proposed an $\cO(|T|^{\omega} \log d)$-time algorithm to solve this problem by applying the BEST theorem to compute the largest $d$ for which $\#ET(G)\geq z$, where $G$ is the order-$d$ de Bruijn graph of $T$. Our algorithm for directed graphs can directly solve the same problem in $O(|T|z \log d)$ 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 {\em node-distinct} if their node sequences are different. This problem has been very recently posed by Bernardini et al.~[ALENEX 2020]. It can be solved in $O(n^{\omega})$ arithmetic operations by applying the well-known BEST theorem, where $\omega<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 $\#ET(G) \geq z$ that does not resort to the BEST theorem and has a cost that is predictably bounded as a function of $m$ and $z$. We address this challenge by providing an algorithm requiring $O(m\cdot \min\{z, \#ET(G)\})$ time. This gives a time-optimal algorithm for $z=O(1)$ or for $\#ET(G)=O(1)$. The impact of this theoretical result on real-world graphs is striking: a simple implementation of our algorithm takes tens of seconds to assess $\#ET(G) \geq z$, whereas a highly-optimized implementation of the BEST theorem requires more than 12 hours. The most surprising consequence of our techniques for directed graphs is that they extend straightforwardly to undirected graphs, for which the underlying counting problem is \#P-complete [Brightwell and Winkler, ALENEX/ANALCO 2005]: we provide an algorithm for assessing $\#ET(G) \geq z$ in an undirected multigraph $G$ requiring time polynomial in $m$ and in $z$. Bernardini et al.~reduced the following problem on strings to the aforementioned assessment problem for directed graphs: Given a string $T$ and an integer $z$, find the largest $d$ such that there exist at least $z$ strings having the same multiplicities of length-$d$ substrings as $T$. The authors proposed an $\cO(|T|^{\omega} \log d)$-time algorithm to solve this problem by applying the BEST theorem to compute the largest $d$ for which $\#ET(G)\geq z$, where $G$ is the order-$d$ de Bruijn graph of $T$. Our algorithm for directed graphs can directly solve the same problem in $O(|T|z \log d)$ time.

M3 - Other contribution

ER -

King's College London - Homepage

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454