The Complexity of Transitively Orienting Temporal Graphs

DOI10.4230/LIPICS.MFCS.2021.75MaRDI QIDQ6168495zbMATH OpenOpenAlexFDO

Authors George B. Mertzios, Hendrik Molter, Malte Renken, P. G. Spirakis, Philipp Zschoche

Publication date 8 August 2023

Full work available at URL https://arxiv.org/abs/2102.06783

zbMATH Keywords

NP-hardnesspolynomial-time algorithmsatisfiabilitytemporal graphtransitive closuretransitive orientation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 et al., 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$". 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, we introduce the 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 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$, the orientation is called strictly temporally transitive. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph $mathcalG$ is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether $mathcalG$ 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.

Recommendations

• Connectivity and inference problems for temporal networks
• Connectivity and inference problems for temporal networks
• An introduction to temporal graphs: an algorithmic perspective
• An introduction to temporal graphs: an algorithmic perspective

Cited in

(6)

• On Temporally Connected Graphs of Small Cost
• ON THE HARDNESS OF RECOGNIZING BUNDLES IN TIME TABLE GRAPHS
• Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks
• The complexity of computing optimum labelings for temporal connectivity
• The complexity of transitively orienting temporal graphs
• Algorithms and complexity for path covers of temporal DAGs

This page was built for publication: The Complexity of Transitively Orienting Temporal Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168495)