Fast Assessment of Eulerian Trails in Graphs with Applications

Enumerating or counting combinatorial objects in graphs is a fundamental data mining task. We consider the problem of assessing the number of Eulerian trails in directed graphs, which is formalized as follows: Given a directed graph , with nodes and edges, and an integer , assess whether the number of Eulerian trails of is at least . This problem underlies many applications in domains ranging from data privacy to computational biology, data compression, and transportation networks. Practitioners currently address this problem by applying the famous BEST theorem, which, in fact, counts instead of just assessing whether . Unfortunately, this solution takes arithmetic operations, where denotes the matrix multiplication exponent. Since in most real-world graphs, the number of edges is comparable to the number of nodes, and is moderate in practice, the algorithmic challenge is: Can we solve the problem faster for certain values of and ? We want to design a combinatorial algorithm for assessing whether , which does not resort to the BEST theorem and has a predictably bounded cost as a function of and . We address this challenge as follows. We first introduce a general algorithmic scheme for assessing (and enumerating) Eulerian trails. We then introduce a novel tree data structure to reduce the number of iterations in this general scheme. Finally, we complement the above with further combinatorial insight leading to an algorithm with a worst-case bound of time. Our experiments using six benchmark datasets with multi-million edges from different domains show that our implementations are up to two orders of magnitude faster than the BEST theorem, perform much fewer than iterations and scale near-linearly with in most cases. Our experiments further show that our implementations bring substantial efficiency benefits in a data privacy application which employs the BEST theorem for the assessment.