Research output: Other contribution

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

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

Type | Fast Eulerian Trails Technical Report |

Unpublished | 26 Oct 2020 |

**Fast_Assessment_Eulerian_Trails_TR**Fast_Assessment_Eulerian_Trails_TR.pdf, 782 KB, application/pdf

Uploaded date:26 Oct 2020

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.

No data available

King's College London - Homepage

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