The Time-Expanded Graph and Algorithmic Aspects of Living Temporal Connectivity

This record contains the preprint version of the manuscript entitled “The Time-Expanded Graph and Algorithmic Aspects of Living Temporal Connectivity”. This paper studies the algorithmic aspects of the 21 connectivity notions introduced in the second paper of the series, using the time-expanded graph as a unifying framework. For living temporal graphs with discrete time, we construct the time-expanded graph (G₄ₗ₏) and prove a fundamental equivalence: regular temporal paths correspond bijectively to directed paths in (G₄ₗ₏), with waiting arcs of unit cost per time unit. We consider an additive cost model in which each unit of waiting has cost 1 and each transport step contributes its latency. Under this model, the total temporal cost of a path is equal to the sum of arc weights in the time-expanded graph. This equivalence yields polynomial-time algorithms for all 21 connectivity notions under the explicit-time model, where the time horizon contributes linearly to the input size. The manuscript provides explicit algorithms, complexity bounds, and structural characterisations for instantaneous, interval, regular, connected regular, disconnected regular, connectable discrete, and irregular connectivity notions. It also discusses more complex temporal problems, such as Hamiltonian temporal paths, which are NP-hard, thereby placing the tractable connectivity notions in a broader complexity landscape. Several conjectures on succinct-time representations, fixed-parameter tractability, and compression techniques are proposed. Applications in route planning, delay-tolerant networks, and real-time systems are also discussed. This paper is the third contribution in a twelve-part series on living temporal graphs.