{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T09:20:19Z","timestamp":1765185619462,"version":"3.46.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"\n 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\n \n \\(G=(V,E)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , with\n \n \\(|V|=n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n nodes and\n \n \\(|E|=m\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n edges, and an integer\n \n \\( z \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n assess<\/jats:italic>\n whether the number\n \n \\(\\#ET(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of Eulerian trails of\n \n \\( G \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is at least\n \n \\( z \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . 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,\n counts<\/jats:italic>\n \n \\(\\#ET(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n instead of just assessing whether\n \n \\(\\#ET(G)\\geq z\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Unfortunately, this solution takes\n \n \\(\\mathcal{O}(n^{\\omega})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n arithmetic operations, where\n \n \\(\\omega < 2.373\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the\n matrix multiplication exponent<\/jats:italic>\n . Since in most real-world graphs, the number\n \n \\( m \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of edges is comparable to the number\n \n \\( n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of nodes, and\n \n \\( z \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is moderate in practice, the algorithmic challenge is:\n \n Can we solve the problem faster for certain values of\n \n \\( m \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\( z \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ?\n <\/jats:italic>\n We want to design a combinatorial algorithm for assessing whether\n \n \\(\\#ET(G)\\geq z\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , which does not resort to the BEST theorem and has a predictably bounded cost as a function of\n \n \\( m \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\( z \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . 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\n \n \\(\\mathcal{O}(m\\cdot\\min\\{z,\\#ET(G)\\})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n 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\n \n \\(mz\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n iterations and scale near-linearly with\n \n \\( m \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n 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.\n <\/jats:p>","DOI":"10.1145\/3771997","type":"journal-article","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T16:07:21Z","timestamp":1761149241000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Assessment of Eulerian Trails in Graphs with Applications"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0770-2235","authenticated-orcid":false,"given":"Alessio","family":"Conte","sequence":"first","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7985-4222","authenticated-orcid":false,"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0888-5061","authenticated-orcid":false,"given":"Grigorios","family":"Loukides","sequence":"additional","affiliation":[{"name":"King\u2019s College London, London, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3915-7665","authenticated-orcid":false,"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands and Vrije Universiteit, Amsterdam, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8738-1595","authenticated-orcid":false,"given":"Giulia","family":"Punzi","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]}],"member":"320","published-online":{"date-parts":[[2025,12,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442866"},{"key":"e_1_3_3_3_2","first-page":"1736","volume-title":"Graph Theory","author":"Biggs N. L.","year":"1976","unstructured":"N. L. Biggs, E. K. Lloyd, and R. J. Wilson. 1976. Graph Theory, 1736-1936. Clarendon Press."},{"key":"e_1_3_3_4_2","first-page":"259","volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithmics and Combinatorics (ALENEX\/ANALCO \u201905)","author":"Brightwell G. R.","year":"2005","unstructured":"G. R. Brightwell and P. Winkler. 2005. Counting Eulerian circuits is #P-complete. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithmics and Combinatorics (ALENEX\/ANALCO \u201905). SIAM, Vancouver, BC, Canada, 259\u2013262."},{"key":"e_1_3_3_5_2","first-page":"149","volume-title":"Classic Papers in Combinatorics","author":"van Aardenne-Ehrenfest T.","year":"1987","unstructured":"T. van Aardenne-Ehrenfest and N. G. de Bruijn. 1987. Circuits and trees in oriented linear graphs. In: Classic Papers in Combinatorics. Branko Gr\u00fcnbaum and G. C. Shephard (Eds.), Springer, Boston, MA, 149\u2013163."},{"key":"e_1_3_3_6_2","first-page":"199","volume-title":"Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX \u201920)","author":"Bernardini G.","year":"2020","unstructured":"G. Bernardini, H. Chen, G. Fici, G. Loukides, and S. P. Pissis. 2020. Reverse-safe data structures for text indexing. In Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX \u201920). SIAM, 199\u2013213."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-11-21"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.2862"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/1.9781611977653.ch33","volume-title":"Proceedings of the 2023 SIAM International Conference on Data Mining (SDM \u201923)","author":"Punzi G.","year":"2023","unstructured":"G. Punzi, A. Conte, R. Grossi, and A. Marino. 2023. An efficient algorithm for assessing the number of ST-paths in large graphs. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM \u201923). Shashi Shekhar, Zhe Zhou, Yizhou Chiang, and Gregor Stiglic (Eds.), SIAM, 289\u2013297."},{"key":"e_1_3_3_10_2","first-page":"1320","volume-title":"Proceedings of the 37th IEEE International Conference on Data Engineering (ICDE \u201921)","author":"Lai Z.","year":"2021","unstructured":"Z. Lai, Y. Peng, S. Yang, X. Lin, and W. Zhang. 2021. PEFP: Efficient k-hop constrained s-t simple path enumeration on FPGA. InProceedings of the 37th IEEE International Conference on Data Engineering (ICDE \u201921). IEEE, 1320\u20131331."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339724"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_3_3_13_2","first-page":"115","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201917)","author":"Conte A.","unstructured":"A. Conte, D. Firmani, C. Mordente, M. Patrignani, and R. Torlone. 2017. Fast enumeration of large k-plexes. InProceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201917). ACM, New York, NY, 115\u2013124."},{"key":"e_1_3_3_14_2","first-page":"345","volume-title":"Proceedings of the 31st ACM International Conference on Information & Knowledge Management (CIKM \u201922)","author":"Dai Q.","unstructured":"Q. Dai, R.-H. Li, H. Qin, M. Liao, and G. Wang. 2022. Scaling up maximal k-plex enumeration. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management (CIKM \u201922). ACM, New York, NY, 345\u2013354."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3269460"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1226"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_3_18_2","first-page":"129","volume-title":"Proceedings of the 4th International Workshop on Algorithms and Models for the Web-Graph (WAW \u201907)","author":"Bader D. A.","unstructured":"D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. 2007. Approximating betweenness centrality. In Proceedings of the 4th International Workshop on Algorithms and Models for the Web-Graph (WAW \u201907). A. Bonato and F. R. K. Chung (Eds.), Lecture Notes in Computer Science, Vol. 4863, Springer-Verlag, Berlin, Heidelberg, 129\u2013137."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649134"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3182392"},{"issue":"5","key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3441299","article-title":"Tiered sampling: An efficient method for counting sparse motifs in massive graph streams","volume":"15","author":"Stefani L. D.","year":"2020","unstructured":"L. D. Stefani, E. Terolli, and E. Upfal. 2020. Tiered sampling: An efficient method for counting sparse motifs in massive graph streams. ACM Transactions on Knowledge Discovery from Data 15, 5 (2021), Article 79, 1\u201352.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3441487"},{"key":"e_1_3_3_23_2","first-page":"16","volume-title":"Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201908)","author":"Becchetti L.","unstructured":"L. Becchetti, P. Boldi, C. Castillo, and A. Gionis. 2008. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201908). ACM, New York, NY, 16\u201324."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365676"},{"key":"e_1_3_3_25_2","first-page":"887","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC \u201912)","author":"Williams V. V.","year":"2012","unstructured":"V. V. Williams. 2012. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC \u201912). ACM, New York, NY, 887\u2013898."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90068-0"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3461698"},{"key":"e_1_3_3_30_2","unstructured":"Eigen library. 2020. Eigen: C++ Template Library for Linear Algebra. Retrieved from http:\/\/eigen.tuxfamily.org"},{"key":"e_1_3_3_31_2","first-page":"162","volume-title":"Proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT \u201921)","author":"Conte A.","unstructured":"A. Conte, G. Loukides, N. Pisanti, S. P. Pissis, and G. Punzi. 2021. Beyond the BEST theorem: Fast assessment of Eulerian trails. In Proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT \u201921). E. Bampis and A. Pagourtzis (Eds.), Lecture Notes in Computer Science, Vol. 12867, Springer-Verlag, Berlin, 162\u2013175."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207024"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/1765751.1765800"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3158063"},{"issue":"1","key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/3418683","article-title":"Combinatorial algorithms for string sanitization","volume":"15","author":"Bernardini G.","year":"2021","unstructured":"G. Bernardini, H. Chen, A. Conte, R. Grossi, G. Loukides, N. Pisanti, S. P. Pissis, G. Rosone, and M. Sweering. 2021. Combinatorial algorithms for string sanitization. ACM Transactions on Knowledge Discovery from Data 15, 1 (2021), Article 8, 1\u201334.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.171285098"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1995.2.275"},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS \u201916)","author":"Kupferman O.","year":"2016","unstructured":"O. Kupferman and G. Vardi. 2016. Eulerian paths with regular constraints. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS \u201916). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 58, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"issue":"1","key":"e_1_3_3_39_2","first-page":"19","article-title":"Positional sequencing by hybridization","volume":"12","author":"Hannenhalli S.","year":"1996","unstructured":"S. Hannenhalli, W. Feldman, H. F. Lewis, S. S. Skiena, and P. A. Pevzner. 1996. Positional sequencing by hybridization. Computer Applications in the Biosciences 12, 1 (1996), 19\u201324.","journal-title":"Computer Applications in the Biosciences"},{"issue":"4","key":"e_1_3_3_40_2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1089\/106652701752236188","article-title":"On the complexity of positional sequencing by hybridization","volume":"8","author":"Ben-Dor A.","year":"2002","unstructured":"A. Ben-Dor, I. Pe\u2019er, R. Shamir, and R. Sharan. 2002. On the complexity of positional sequencing by hybridization. Journal of Computational Biology: A Journal of Computational Molecular Cell Biology 8, 4 (2002), 361\u2013371. DOI:","journal-title":"Journal of Computational Biology: A Journal of Computational Molecular Cell Biology"},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/1835804.1835873","article-title":"Neighbor query friendly compression of social networks","author":"Maserrat H.","year":"2010","unstructured":"H. Maserrat, J. Pei. 2010. Neighbor query friendly compression of social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201910). ACM, New York, NY, 533\u2013542.","journal-title":"Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201910)"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/110834810"},{"volume-title":"Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM \u201922)","author":"Bernardini G.","key":"e_1_3_3_43_2","unstructured":"G. Bernardini, H. Chen, G. Loukides, S. P. Pissis, L. Stougie, and M. Sweering. 2022. Making de Bruijn graphs Eulerian. InProceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM \u201922). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 223, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures: A Practical Approach","author":"Navarro G.","year":"2016","unstructured":"G. Navarro. 2016. Compact Data Structures: A Practical Approach (1st ed.). Cambridge University Press, Cambridge, UK.","edition":"1"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316335"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"e_1_3_3_48_2","unstructured":"P. Ferragina and G. Navarro.Pizza & Chili Corpus\u2014Compressed Indexes and Their Testbeds. Retrieved from http:\/\/pizzachili.dcc.uchile.cl\/texts.html"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771997","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T09:19:21Z","timestamp":1765185561000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3771997"],"URL":"https:\/\/doi.org\/10.1145\/3771997","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2025,12,8]]},"assertion":[{"value":"2024-08-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}