The complexity of transitively orienting temporal graphs
George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, Philipp Zschoche · Journal of Computer and System Sciences · 2025
In a temporal network with discrete time-labels on its edges, information can only "flow" along sequences of edges with non-decreasing (resp.increasing) time-labels.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.By 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.Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a temporal graph G is transitively orientable.In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether G is strictly transitively orientable.Additionally we introduce further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.