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 G = (V, E), with |V| = n nodes and |E| = m edges, and an integer z, assess whether the number #ET(G) of Eulerian trails of G is at least z. 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 #ET(G) instead of just assessing whether #ET(G) ≥ z. Unfortunately, this solution takes O(nω) arithmetic operations, where ω < 2.373 denotes the matrix multiplication exponent. Since in most real-world graphs, the number m of edges is comparable to the number n of nodes, and z is moderate in practice, the algorithmic challenge is: Can we solve the problem faster for certain values ofm andz? 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 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 O(m · min{z, #ET(G)}) 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 mz iterations and scale near-linearly with m 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.

• View at Publisher

Free Full Text ( Final Version , 3mb )