Computing and Listing st-Paths in Public Transportation Networks

Given a set of directed paths (called lines) L, a public transportation network is a directed graph G_L=(V_L,A_L) which contains exactly the vertices and arcs of every line l∈L. An st-route is a pair (π,γ) where γ=<l_1,...,l_h> is a line sequence and π is an st-path in G_L which is the concatenation of subpaths of the lines l_1,...,l_h, in this order. We study three related problems concerning traveling from s to t in G_L. We present an optimal algorithm for computing an st-route (π,γ) where |γ| (i.e., the number of line changes plus one) is minimum among all st-routes. We show for the problem of finding an st-route (π,γ) that minimizes the number of different lines in γ, even computing an o(log |V|)-approximation is NP-hard. Finally, given a constant integer β, we present an algorithm for listing all st-paths π for which a route (π,γ) with |γ|≤β exists, and show that the running time of this algorithm is polynomial with respect to the input and the output size.