Abstract
In a temporal network with discrete timelabels on its edges, entities and information can only "flow" along sequences of edges whose timelabels are nondecreasing (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 timelabeled edges remain undirected: an edge e = {u,v} with timelabel t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. 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 in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with timelabel t₁ and v has a directed edge towards w with timelabel t₂ ≥ t₁, then u also has a directed edge towards w with some timelabel t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomialtime algorithm for recognizing whether a given temporal graph ? is transitively orientable. In wide contrast we prove that, surprisingly, it is NPhard to recognize whether ? 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.
BibTeX  Entry
@InProceedings{mertzios_et_al:LIPIcs.MFCS.2021.75,
author = {Mertzios, George B. and Molter, Hendrik and Renken, Malte and Spirakis, Paul G. and Zschoche, Philipp},
title = {{The Complexity of Transitively Orienting Temporal Graphs}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {75:175:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14515},
URN = {urn:nbn:de:0030drops145157},
doi = {10.4230/LIPIcs.MFCS.2021.75},
annote = {Keywords: Temporal graph, transitive orientation, transitive closure, polynomialtime algorithm, NPhardness, satisfiability}
}
Keywords: 

Temporal graph, transitive orientation, transitive closure, polynomialtime algorithm, NPhardness, satisfiability 
Collection: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 
Issue Date: 

2021 
Date of publication: 

18.08.2021 