Efficient Label-Constrained Path Queries on Time-Dependent Graphs via LP-Tree Decomposition

Shortest path queries are among the most fundamental operations in graph processing. Prior studies have extensively examined label-constrained queries on static graphs with fixed edge weights. However, real-world networks exhibit temporal dynamics and often contain complex heterogeneous structures. Examples include peak-hour variations in travel time and the coordination of multiple transportation modes. These time-dependent and label-dependent characteristics limit the applicability of existing methods to the Time-Dependent Label-Constrained Shortest Path (TD-LCSP) problem. To address this limitation, we propose LP-Tree, a label-partitioned tree decomposition framework that models both label constraints and temporal dependencies in a unified manner. Based on this structure, we design the Parameter-Separated (PS) Index, which decouples key parameters to improve query efficiency and reduce storage costs. The combined approach significantly lowers space consumption and achieves sub-millisecond query latency on large-scale time-dependent graphs. Extensive experiments on multiple datasets demonstrate the effectiveness and efficiency of our proposed approach.