Counting the Number of Hop-Constrained Simple S-T Paths in Large Graphs

Graphs are widely used to model complex relationships among entities in domains such as recommendation systems and social networks. A fundamental problem in these applications is quantifying the connectivity between two entities, often formulated as estimating the number of source-to-target (s–t) paths under specific constraints. In this paper, we study the problem of hop-constrained s–t path counting, which aims to estimate the number of paths from a source vertex s to a target vertex t within a given hop bound k. We propose kPathAssess, an efficient path counting algorithm inspired by the recent PathAssess algorithm. kPathAssess balances estimation accuracy and computational complexity by leveraging locally computable lower bounds on path counts. Extensive experiments on real-world graphs demonstrate that kPathAssess achieves high estimation efficiency with significantly reduced computation time, particularly as the hop constraint increases.