Abstract
In traditional graph theory, relationships between entities are typically treated as static. However, modern systems—ranging from social networks and mobile ad-hoc sensors to transportation infrastructure—are inherently dynamic. This paper provides a foundational survey of temporal graphs, where the network topology evolves over discrete time steps. By introducing a temporal dimension, classical graph-theoretic assumptions are challenged: fundamental theorems fail, and problems that are computationally efficient in static contexts often become NP-hard. This survey outlines the essential modeling techniques, algorithmic strategies, and the structural complexities inherent in time-varying networks.
Introduction
Most real-world networks are not frozen in time. In a communication network, a link might only exist when two devices are within range; in a social network, an interaction occurs at a specific timestamp. Othon Michail’s survey addresses the need for a unified algorithmic framework to handle these dynamic systems. The core distinction in temporal graphs is the requirement for time-respecting paths, or "journeys." Unlike a static path, a journey is only valid if the sequence of edges used occurs at non-decreasing (or strictly increasing) time steps. This simple constraint necessitates a complete rethink of connectivity, reachability, and optimization.
Modeling and Methodology
Formalisms
A temporal graph is typically modeled as a sequence of static graphs $G_1, G_2, \dots, G_l$ over a fixed set of nodes $V$. Each edge is assigned a "label" or a set of labels representing the discrete time steps when that edge is active. For systems with extremely long lifetimes, the paper explores succinct representations, where edge availability is defined by linear functions (e.g., $f(x) = ax + b$), allowing for algorithmic analysis that does not scale linearly with the total duration of the system.
The Static Expansion Technique
The primary tool for analyzing temporal graphs is the static expansion. This method transforms a temporal graph into a large, multi-layered Directed Acyclic Graph (DAG). Each layer in the DAG represents the state of the network at a specific time step. "Vertical" edges are added to allow nodes to "wait" for the next time step. While this transformation allows researchers to apply standard static algorithms to temporal problems, it comes at the cost of a significant increase in graph size, often proportional to the lifetime of the network.
Key Insights: The Complexity of Time
The Failure of Classical Theorems
One of the most striking revelations in temporal graph theory is the failure of Menger’s Theorem. In static graphs, the maximum number of node-disjoint paths between two vertices is equal to the minimum number of nodes whose removal disconnects them. In the temporal domain, this equivalence breaks down. To address this, the survey introduces the concept of "out-disjointness"—a condition where journeys are considered disjoint only if they do not leave the same node at the same time step.
Computational Hardness
Temporal constraints often lead to a "complexity explosion." Problems that reside in the complexity class P for static graphs frequently become NP-complete or PSPACE-complete in temporal graphs. For instance:
- Maximum Matching: Finding the largest set of edges that do not share a vertex is significantly more difficult when those edges are only available at specific moments.
- Traveling Salesman Problem (TSP): The temporal version of TSP is notably harder to approximate. While static TSP has a $1.5$ approximation factor, the temporal version (with costs of 1 and 2) currently only allows for a $(1.7 + \epsilon)$ approximation.
Temporality as a Metric
The paper introduces "temporality" as a formal metric: the minimum number of labels required per edge to maintain specific connectivity properties, such as all-pairs reachability. This metric helps quantify how much "dynamicity" is required for a network to function effectively.
Algorithmic Results and Information Flow
Journey Computation
The survey highlights an efficient offline algorithm for computing foremost journeys (the earliest possible arrival time from a source to all other nodes). This temporal adaptation of Breadth-First Search (BFS) operates in $O(n\alpha^3(\lambda) + |\lambda|)$ time, where $\lambda$ represents the set of labels.
Random Temporal Graphs
Applying the Erdős-Rényi $G(n, p)$ model to temporal contexts reveals interesting phase transitions. In random temporal cliques where edges are assigned random time labels, the temporal diameter (the time required to reach any node from any other) is shown to be $\Theta(\log n)$ with high probability. Furthermore, the paper establishes bounds for the emergence of journeys of length $k$ based on the number of nodes and available time slots.
Limitations and Future Directions
As a field in its infancy, temporal graph theory faces several challenges:
- Standardization: There is currently a lack of uniform terminology and competing models (discrete vs. continuous time).
- Approximation Gaps: Significant work is needed to close the gap between the approximation ratios of temporal algorithms and their static counterparts.
- Online vs. Offline Models: Most existing research assumes "offline" knowledge, where the entire schedule of the graph is known in advance. Future research must focus on online or distributed algorithms where the topology is revealed incrementally.
By formalizing the "cost of time," this survey provides a roadmap for moving beyond static abstractions toward a more accurate algorithmic representation of our dynamic world.
Summary updated