【Abstract】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 the A-BiBFS++ 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 on A-BiBFS++, we propose the EVE method to tackle the second problem, which exploits the paradigm of edge-wise examination rather than exhaustively enumerating all simple paths. Extensive experiments show that both A-BiBFS++ and EVE significantly outperform all baselines. Moreover, by taking EVE 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.