Generating kk-Hop-Constrained ss-tt Path Graphs
Yuzheng Cai, Siyuan Liu, Weiguo Zheng, Xuemin Lin, Chengbo Zhang, Xuecang Zhang · IEEE Transactions on Knowledge and Data Engineering · 2025
In this paper, we study two different problems that investigate relations between given vertices$s$and$t$. The first problem is to generate the$k$-hop-constrained$s$-$t$path graph, i.e., the subgraph consisting of all paths from$s$to$t$, where each path is not longer than$k$s.t.$s$and$t$appear only once. To solve the first problem, we propose theA-BiBFS$^{++}$t++method enhanced with the reduced neighbor index and an approximate vertex grouping strategy. The second problem is to generate the$k$-hop-constrained$s$-$t$simple path graph, i.e., the subgraph consisting of all$k$-hop-constrained simple paths from$s$to$t$, which is proved to be NP-hard on directed graphs. Based onA-BiBFS$^{++}$t++, we propose theEVEmethod to tackle the second problem, which exploits the paradigm of edge-wise examination rather than exhaustively enumerating all simple paths. Extensive experiments show that bothA-BiBFS$^{++}$s++andEVEsignificantly outperform all baselines. Moreover, by takingEVEas a built-in block, state-of-the-art for hop-constrained simple path enumeration can be accelerated by up to an order of magnitude.