The Complexity of Transitively Orienting Temporal Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915124417134592 |
|---|---|
| author | Mertzios, George B. Molter, Hendrik Renken, Malte Spirakis, Paul G. Zschoche, Philipp |
| author_facet | Mertzios, George B. Molter, Hendrik Renken, Malte Spirakis, Paul G. Zschoche, Philipp |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_06783 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Complexity of Transitively Orienting Temporal Graphs Mertzios, George B. Molter, Hendrik Renken, Malte Spirakis, Paul G. Zschoche, Philipp Data Structures and Algorithms Computational Complexity Discrete Mathematics 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. |
| title | The Complexity of Transitively Orienting Temporal Graphs |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2102.06783 |