{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:38:17Z","timestamp":1768030697651,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U20B2046"],"award-info":[{"award-number":["U20B2046"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Graphs have been widely used in real-world applications, in which investigating relations between vertices is an important task. In this paper, we study the problem of generating the k-hop-constrained s-t simple path graph, i.e., the subgraph consisting of all simple paths from vertex s to vertex t of length no larger than k. To our best knowledge, we are the first to formalize this problem and prove its NP-hardness on directed graphs. To tackle this challenging problem, we propose an efficient algorithm namedEVE, which exploits the paradigm of edge-wise examination rather than exhaustively enumerating all paths. Powered by essential vertices appearing in all simple paths between vertex pairs,EVE distinguishes the edges that are definitely (or not) contained in the desired simple path graph, producing a tight upper-bound graph in the time cost O(k2|E|). Each remaining undetermined edge is further verified to deliver the exact answer. Extensive experiments are conducted on 15 real networks. The results show thatEVE significantly outperforms all baselines by several orders of magnitude. Moreover, by takingEVE as a built-in block, state-of-the-art for hop-constrained simple path enumeration can be accelerated by up to an order of magnitude.<\/jats:p>","DOI":"10.1145\/3588915","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":8,"title":["Towards Generating Hop-constrained s-t Simple Path Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7096-5328","authenticated-orcid":false,"given":"Yuzheng","family":"Cai","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6002-3779","authenticated-orcid":false,"given":"Siyuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1200-7368","authenticated-orcid":false,"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Daniel Damir Harabor, and P. Kilby","author":"Ahmadi Saman","year":"2021","unstructured":"Saman Ahmadi, Guido Tack, Daniel Damir Harabor, and P. Kilby. 2021. A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem. In AAAI."},{"key":"e_1_2_2_2_1","volume-title":"Orlin","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868241"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_25"},{"key":"e_1_2_2_6_1","volume-title":"Linked Open Data System for Scientific Data Sets. In IPaMin 2014 (CEUR Workshop Proceedings","author":"Frederik Simon","year":"2014","unstructured":"Frederik Simon B\"a umer, Jangwon Gim, Do-Heon Jeong, Michaela Geierhos, and Hanmin Jung. 2014. Linked Open Data System for Scientific Data Sets. In IPaMin 2014 (CEUR Workshop Proceedings, Vol. 1292)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.134"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21960"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-73216-5_6"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0346-6"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2956557"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.04.018"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_2_16_1","volume-title":"Ismael Navas Delgado, and Jos\u00e9 Francisco Aldana Montes","author":"Godoy Mar'i","year":"2011","unstructured":"Mar'i a Jes\u00fa s Garc'i a-Godoy, Ismael Navas Delgado, and Jos\u00e9 Francisco Aldana Montes. 2011. Bioqueries: a social community sharing experiences while querying biological linked data. In SWAT4LS 2011. 24--31."},{"key":"e_1_2_2_17_1","volume-title":"symposium on discrete algorithms","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. symposium on discrete algorithms (2005)."},{"key":"e_1_2_2_18_1","volume-title":"Encyclopedia of Algorithms. 640--645.","author":"Grossi Roberto","unstructured":"Roberto Grossi. 2016. Enumeration of Paths, Cycles, and Spanning Trees. In Encyclopedia of Algorithms. 640--645."},{"key":"e_1_2_2_19_1","volume-title":"LATIN","volume":"10807","author":"Grossi Roberto","year":"2018","unstructured":"Roberto Grossi, Andrea Marino, and Luca Versari. 2018. Efficient Algorithms for Listing k Disjoint st-Paths in Graphs. In LATIN 2019, Vol. 10807. 544--557."},{"key":"e_1_2_2_20_1","volume-title":"RelFinder: Revealing Relationships in RDF Knowledge Bases. In SAMT","volume":"5887","author":"Heim Philipp","year":"2009","unstructured":"Philipp Heim, Sebastian Hellmann, Jens Lehmann, Steffen Lohmann, and Timo Stegemann. 2009. RelFinder: Revealing Relationships in RDF Knowledge Bases. In SAMT 2009, Vol. 5887. 182--187."},{"key":"e_1_2_2_21_1","volume-title":"Combining speed-up techniques for shortest-path computations. ACM Journal of Experimental Algorithms","author":"Holzer Martin","year":"2005","unstructured":"Martin Holzer, Frank Schulz, Dorothea Wagner, and Thomas Willhalm. 2005. Combining speed-up techniques for shortest-path computations. ACM Journal of Experimental Algorithms (2005)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_2_2_24_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection."},{"key":"e_1_2_2_25_1","volume-title":"Hop-Constrained Subgraph Query and Summarization on Large Graphs. In DASFAA 2021 International Workshops - BDQM, GDMA, MLDLDSA, MobiSocial, and MUST","volume":"12680","author":"Liu Yu","year":"2021","unstructured":"Yu Liu, Qian Ge, Yue Pang, and Lei Zou. 2021. Hop-Constrained Subgraph Query and Summarization on Large Graphs. In DASFAA 2021 International Workshops - BDQM, GDMA, MLDLDSA, MobiSocial, and MUST, Vol. 12680. 123--139."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1719970.1720052"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00674-5"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_2_31_1","volume-title":"IWOCA","volume":"8986","author":"Rizzi Romeo","year":"2014","unstructured":"Romeo Rizzi, Gustavo Sacomoto, and Marie-France Sagot. 2014. Efficiently Listing Bounded Length st-Paths. In IWOCA 2014, Vol. 8986. 318--329."},{"key":"e_1_2_2_32_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI 2015. 4292--4293."},{"key":"e_1_2_2_33_1","volume-title":"Routing on Multiple Optimality Criteria. In SIGCOMM '20","author":"Luis Sobrinho Jo","year":"2020","unstructured":"Jo a o Luis Sobrinho and Miguel Alves Ferreira. 2020. Routing on Multiple Optimality Criteria. In SIGCOMM '20. 211--225."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457290"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_2_2_37_1","volume-title":"Efficient Breadth-First Search on Massively Parallel and Distributed-Memory Machines. Data Science and Engineering","author":"Ueno Koji","year":"2017","unstructured":"Koji Ueno, Toyotaro Suzumura, Naoya Maruyama, Katsuki Fujisawa, and Satoshi Matsuoka. 2017. Efficient Breadth-First Search on Massively Parallel and Distributed-Memory Machines. Data Science and Engineering (2017)."},{"key":"e_1_2_2_38_1","first-page":"511","article-title":"Reachability Queries in Very Large Graphs","volume":"2014","author":"Veloso Ren\u00ea Rodrigues","year":"2014","unstructured":"Ren\u00ea Rodrigues Veloso, Lo\"i c Cerf, Wagner Meira Jr., and Mohammed J. Zaki. 2014. Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach. In EDBT 2014. 511--522.","journal-title":"A Fast Refined Online Search Approach. In EDBT"},{"key":"e_1_2_2_39_1","volume-title":"Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks. In SIGMOD '21","author":"Wang Ye","year":"2021","unstructured":"Ye Wang, Qing Wang, Henning Koehler, and Yu Lin. 2021. Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks. In SIGMOD '21. 1946--1958."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.536364"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0468-3"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2017.02.009"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICInfA.2015.7279596"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186115"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505724"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1100\/2012\/315797"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0256-4"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0495-8"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588915"],"URL":"https:\/\/doi.org\/10.1145\/3588915","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}