Lightweight 2-Hop Labels for Reachability Queries on Large-Scale Graphs

Reachability queries are a fundamental problem in graph analysis. To avoid the high cost of traversal-based methods, indexing techniques have been widely studied, among which 2-hop labeling is particularly attractive due to its simplicity and query efficiency. However, maintaining reachability information for all vertices often leads to prohibitively large index sizes. Existing approaches mainly reduce index size either through carefully designed construction orders or by compressing the graph structure, but ordering-based methods suffer from limited scalability, while compression-based methods may lose reachability information. To address these issues, we propose a contraction-based 2-hop indexing framework that integrates vertex contraction into index construction, reducing the number of iterations while preserving complete reachability information on the original graph. We further design a dominance-aware contraction order and pruning strategies to significantly reduce index size. Extensive experiments on real-world datasets show that our method reduces index size by 1-2 orders of magnitude compared to state-of-the-art approaches, while maintaining comparable index construction and query performance.