Abstract
In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge $e=\{u,v\}$ with time-label $t$ specifies that "$u$ communicates with $v$ at time $t$". In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior. An orientation of a temporal graph is called temporally transitive if, whenever $u$ has a directed edge towards $v$ with time-label $t_1$ and $v$ has a directed edge towards $w$ with time-label $t_2\geq t_1$, then $u$ also has a directed edge towards $w$ with some time-label $t_3\geq t_2$. If we just demand that this implication holds whenever $t_2 > t_1$, we call the orientation strictly temporally transitive, as it is based on the strict directed temporal path from $u$ to $w$. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph $\mathcal{G}$ is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether $\mathcal{G}$ is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.
Introduction
In static graph theory, the concept of transitive orientation is fundamental. A graph is transitively orientable if its edges can be directed such that whenever there are directed edges $(u, v)$ and $(v, w)$, there is also a directed shortcut $(u, w)$. Such graphs, known as comparability graphs, have well-understood algorithmic properties. However, real-world networks—from social interactions to biological pathways—are often temporal, with edges appearing at specific time points. In these networks, information flows along temporal paths where time labels are non-decreasing. This research extends the notion of transitive orientation to the temporal domain, revealing a striking complexity gap between standard and strict definitions of transitivity.
Defining Temporal Transitivity
A temporal graph $\mathcal{G}$ consists of a set of vertices and a set of edges, each associated with a discrete time label. The authors introduce the Temporal Transitive Orientation (TTO) problem: can we orient the edges of $\mathcal{G}$ such that if $u \to v$ at time $t_1$ and $v \to w$ at time $t_2 \ge t_1$, then there exists an edge $u \to w$ at some time $t_3 \ge t_2$?
A variant is Strict TTO, which only requires this transitive shortcut when the path is strictly increasing in time ($t_2 > t_1$). While this seems like a minor distinction, it fundamentally alters the problem's complexity, leading to what the authors call a "strictness paradox."
The Algorithmic Divide
The core contribution of this work is identifying the complexity gap between these two definitions. The authors prove that while TTO can be solved in polynomial time, Strict TTO is NP-hard. This is surprising because "strict" versions of graph problems typically do not jump complexity classes.
The difficulty in TTO arises primarily from "synchronous triangles"—sets of three edges with identical time labels. These create constraints similar to Not-All-Equal 3-SAT (NAE-3SAT), which is generally NP-hard. However, the specific structure of TTO allows for a specialized polynomial-time algorithm that combines 2-SAT forcing with a greedy approach to resolve these synchronous constraints. In contrast, the Strict TTO problem remains intractable even under severe restrictions, such as when the temporal graph uses only four distinct time labels.
Methodology and Forcing Relations
The researchers utilize a "forcing relation" ($\Lambda$) to track how orienting one edge necessitates the orientation of others to maintain transitivity. For TTO, these relations are translated into Boolean formulas. While most constraints map to 2-SAT, synchronous edges introduce NAE-3SAT components. The paper's primary algorithmic achievement is a procedure that iteratively "forces" variables and checks for contradictions, successfully navigating this mix of constraints in polynomial time.
Key Results and Extensions
Beyond recognition, the paper explores the Temporal Transitive Completion (TTC) problem—adding the minimum number of edges to make a graph transitively orientable. They find that while TTC is NP-hard in general, it becomes solvable in $O(m^2)$ time if the edges are already oriented. They also investigate Multilayer Transitive Orientation (MTO), finding it NP-complete even if each edge appears in at most two time layers.
Conclusion
This research provides a comprehensive map of the complexity landscape for temporal transitive orientations. The discovery of a polynomial-time algorithm for TTO alongside the NP-hardness of Strict TTO highlights the subtle but profound impact of temporal constraints on graph algorithms. Future work remains in finding a compact set of forbidden subgraphs to characterize these graphs and optimizing these algorithms for large-scale real-world temporal networks.
Summary updated