Source-linked AI summary
An Introduction to Temporal Graphs: An Algorithmic Perspective
Othon Michail
TL;DR
Temporal graphs extend static graph analysis to changing relationships, but lack established structural and algorithmic principles. This survey synthesizes applications, modeling tools, algorithms, complexity results, and temporal reformulations of classical problems, including both strong negative results and positive special-case guarantees.
Problem
Temporal graph theory still lacks a concrete set of structural and algorithmic principles, while the complexity impact of adding time to combinatorial problems remains unclear.
Method
The paper surveys temporal-graph applications and results, including static expansion into directed acyclic graphs and temporal adaptations of classical algorithms and theorems.
Results
The survey reports that temporal problems can exhibit strong inapproximability, while temporal reformulations can recover valid results such as Menger’s theorem and efficient foremost-journey computation.
Takeaways & Limitations
Temporal graphs provide a common model for dynamic communication, social, transportation, and physical networks, motivating specialized theory and tools beyond static-graph methods.
Takeaways & Limitations
Whether a (3/2)-factor approximation exists for general TTSP(1,2) or its lifetime-n special case remains open.
Abstract
from arXiv · showhide
A \emph{temporal graph} is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence $G_1,G_2\ldots,G_l$ of static graphs over the same (static) set of nodes $V$. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.
1 Introduction
Temporal graphs extend graph theory by representing time-varying relationships, motivating new structural principles and algorithms. The survey organizes recent results across applications, models, and temporal versions of classical problems.
- Temporal graphs model changing relationships among fixed entities and can represent information, communication, social, transportation, and physical networks.
- The survey also points to distributed dynamic networks, random temporal graphs, and temporal models based on linear-function edge availability.
- Formal temporal-graph theory remains underdeveloped despite extensive study of static graphs, with the complexity impact of adding time still unclear.
- Temporal generalizations can differ radically from static problems: Menger’s theorem fails for node-disjoint journeys, while computing their number is NP-complete.
- Research has addressed temporal network design through temporality and temporal cost, which minimize respectively the maximum labels per edge and total labels used.
- Temporal analogues of TSP, matching, path packing, Max-TSP, and cycle cover exhibit strong inapproximability, alongside positive results for special cases.
2 Modeling and Basic Properties
The paper formalizes discrete temporal graphs as labeled static graphs or time-edge structures and provides equivalent snapshot and static-expansion views. It defines time-respecting journeys and describes an efficient offline algorithm for foremost journeys.
- A discrete temporal graph is a static graph whose edges carry zero or more natural-number labels denoting availability times.
- The labeling notation supports total label count, minimum and maximum labels, and graph age, defined as λmax − λmin + 1.
- A temporal graph can be represented by time-edges, whose time-indexed sets define static snapshots, or as a sequence of static graph instances.
- Static expansion creates time-node copies at successive levels and connects each node to its next copy and to neighbors available at that time.
- A journey is a path using strictly increasing edge labels; its duration, departure time, arrival time, foremost status, temporal distance, and dynamic diameter are defined accordingly.
- An offline temporal BFS computes foremost journeys from a source and start time in O(nα^3(λ) + |λ|) time.
3 Connectivity and Menger’s Theorem
Temporal constraints invalidate the classical node-based form of Menger’s theorem, even in single-labeled graphs. A time-aware reformulation restores an exact min–max relationship using out-disjoint journeys and node departure-time removals.
- In static graphs, Menger’s theorem equates the maximum number of node-disjoint s-z paths with the minimum separating-node set.
- Temporal graphs violate this equality when paths are replaced by journeys, even when every edge has at most one label.
- A single-labeled construction can have no two node-disjoint s-z journeys while every separator requires at least two nodes; generalized instances use 2k − 1 inner nodes and require separators of size at least k.
- The edge-disjoint analogue remains valid for single-labeled temporal graphs, where edge-disjoint journeys equal the minimum edge-removal cut.
- The temporal reformulation replaces node-disjointness with out-disjointness and node removals with node departure-time removals.
- The temporal Menger analogue states that the maximum number of out-disjoint s-z journeys equals the minimum number of node departure times separating s from z.
4 Dissemination and Gathering of Information
Temporal-graph research studies information dissemination, gathering, and token forwarding under changing connectivity. Results include linear-round gathering under continuous connectivity and strong lower bounds for token dissemination.
- Temporal graphs model gossiping and information dissemination among distributed entities, including telephone, broadcast, and dynamic-network settings.
- The k-token dissemination problem asks algorithms to distribute k distinct tokens to all nodes under any continuously connected topology sequence.
- Ω(n log k) rounds are required by any deterministic centralized token-forwarding algorithm for k-token dissemination in continuously connected temporal graphs.
- Ω(nk/log n) rounds are required by any randomized token-forwarding algorithm, within a logarithmic factor of the O(nk) distributed upper bound.
- O(n) rounds suffice to deliver k tokens to an arbitrary sink in continuously connected temporal graphs using local broadcasts.
- The gathering proof routes tokens along k out-disjoint journeys, allowing parallel forwarding without conflicting outgoing transmissions.
5 Design Problems
Temporal-graph design assigns edge labels to preserve selected static-graph connectivity properties while minimizing temporality or total temporal cost. The survey highlights exact constructions for DAGs and rings, kernel-based lower bounds, and age–temporality trade-offs.
- Design Problems: Temporal network design assigns labels to an underlying graph while preserving selected time-respecting paths or reachabilities.
- Design Problems: Temporality minimizes the maximum labels per edge, whereas temporal cost minimizes the total number of labels.
- Basic constructions: A directed ring has temporality 2 for preserving all simple paths, while a directed acyclic graph has temporality 1.
- Lower bounds: An edge-kernel of size k forces at least k labels on an edge when all static paths must receive temporal analogues.
- Open questions: The survey identifies an open question about which other underlying-graph structures can increase temporality.
- Connectivity properties: Preserving reachability is cheaper than preserving all paths: strongly connected digraphs need at most two labels per edge for one journey per reachable ordered pair.
- Age–temporality trade-off: For a directed ring with age (n −1) + k, all-path temporality is Θ(n/k) for 1 ≤ k ≤ n −1 and n −1 when k = 0.
- Age–temporality trade-off: Restricting the maximum label to the diameter d(G) can force temporality to be at least d(G).
6 Temporal Versions of Other Standard Graph Problems: Complexity and Solutions
Temporal versions of standard graph problems can become substantially harder, with polynomial-time static problems becoming NP-hard or difficult to approximate. The section also presents reductions and approximation algorithms for temporal matching, exploration, and traveling-salesman variants.
- Temporal Matching: Temporal Matching asks whether a maximum matching of the underlying graph can select distinct labels for its edges, and is linked to Balanced Union Labeled Matching.The reduction starts from Balanced 3SAT through Balanced Union Labeled Matching.
- Temporal Exploration: Temporal Exploration is NP-complete although static explorability is decidable in linear time, and it admits no cn-approximation unless P = NP.The stronger inapproximability applies for some constant c > 0.
- Temporal Exploration: A connected-instance reduction yields a (2 −ε)-inapproximability threshold for Temporal Exploration unless P = NP.The reduction uses three strongly connected static graphs T1, T2, and T3 over successive intervals.
- Temporal Exploration: For the exploration reduction, Hamiltonian instances have OPT = n2, whereas non-Hamiltonian instances satisfy OPT ≥ 2n2 + 1.These bounds create the gap used for the hardness result.
- Temporal TSP: TTSP(1,2) transfers temporal variation from topology to edge costs, assigning each time-edge cost 1 or 2 and minimizing the total cost of a temporal tour.The section illustrates an optimum tour of cost 4 in a six-step temporal graph.
- Temporal TSP: Reductions to independent set and set packing yield approximation ratios of 1.7 + ε generally and 13/8 + ε when lifetime equals n.The earlier independent-set approach gives 7/4 + ε generally and 12/7 + ε for lifetime n; a (3/2)-factor approximation remains open.
7 Linear Availabilities
Linear availability functions represent recurring edge appearances compactly, but temporal queries then require arithmetic reasoning rather than lifetime-linear processing. Coincidence questions reduce to modular equations, while simultaneous availability reduces to systems of congruences.
- Model: Each edge receives a linear availability function fe(x) = aex + be, so its appearances are determined by integer values of x.For example, fe(x) = 3x + 4 makes the edge available at the corresponding arithmetic progression of times.
- Model: The lifetime is encoded in binary, making algorithms with at least linear dependence on lifetime unacceptable.The representation can be exponentially shorter than the lifetime itself.
- Pairwise coincidence: Determining whether two edges appear together reduces to testing solvability of a modular linear equation.The equality a1x1 + b1 = a2x2 + b2 becomes a divisibility condition and then a congruence.
- Pairwise coincidence: A modular equation ax ≡ b′ (mod c) has a solution exactly when gcd(a, c) divides b′.All solutions modulo c can be found in O(log c + gcd(a, c)) arithmetic operations.
- Pairwise coincidence: When b1 = b2 = 0, two edges always share an appearance time unless the relevant time exceeds the network lifetime.The foremost common time is computed through lcm(a1, a2), using lcm(a1, a2) = |a1a2|/gcd(a1, a2).
- Multiple-edge coincidence: Simultaneous availability of multiple edges becomes a system t ≡ bi (mod ai), solvable exactly under the pairwise gcd compatibility conditions.If solvable, the solution is unique modulo lcm(a1, a2, . . . , ak), and can be computed using O(lg2 a) bit operations.
8 Random Temporal Graphs
This section analyzes random temporal graphs in which edge labels are chosen probabilistically, deriving bounds on journeys and temporal connectivity. Second-moment arguments show that sufficiently short journeys appear almost surely under broad parameter regimes.
- Random temporal-graph model: Each edge independently chooses one uniformly random time-label from [r], producing a succinct random temporal-graph model.The model assigns every edge of an underlying clique a single label t ∈ [r] with probability r^-1.
- Journey probabilities: For a fixed path, journey assignments are equiprobable, and strictly increasing labelings correspond bijectively to selecting k labels from r available labels.For k = 2 and r = 10, the resulting probability is 9/20.
- Almost-sure journeys: A second-moment analysis bounds dependencies among overlapping paths and shows that the probability of having no length-4 journey is o(1).The argument establishes Var(X) = o([E(X)]^2) and then applies Chebyshev’s inequality.
- Almost-sure journeys: For all r ≥ 4, almost all random temporal graphs contain a journey of length 4.This is the stated theorem obtained from the second-moment argument.
- Almost-sure journeys: For all k = o(√n) and r = Ω(n), almost all random temporal graphs contain a journey of length k.This extends the length-4 result to journeys whose length grows below √n.
- Temporal reachability: For r = Θ(√n), the probability of reaching a target by time 2 approaches a constant, while a constructive argument gives journeys arriving by time Θ(log n) with high probability.The latter guarantee holds simultaneously for all node pairs with failure probability bounded by 3/n.