Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation

Abstract : We consider the problem of assigning appearing times to the edges of a digraph in order to maximize the (average) temporal reachability between pairs of nodes. Motivated by the application to public transit networks, where edges cannot be scheduled independently one of another, we consider the setting where the edges are grouped into certain walks (called trips) in the digraph and where assigning the appearing time to the first edge of a trip forces the appearing times of the subsequent edges. In this setting, we show that, quite surprisingly, it is NP-complete to decide whether there exists an assignment of times connecting a given pair of nodes. This result allows us to prove that the problem of maximising the temporal reachability cannot be approximated within a factor better than some polynomial term in the size of the graph. We thus focus on the case where, for each pair of nodes, there exists an assignment of times such that one node is reachable from the other. We call this property strong temporalisability. It is a very natural assumption for the application to public transit networks. On the negative side, the problem of maximising the temporal reachability remains hard to approximate within a factor √ n/12 in that setting. Moreover, we show the existence of collections of trips that are strongly temporalisable but for which any assignment of starting times to the trips connects at most an O(1/ √ n) fraction of all pairs of nodes. On the positive side, we show that there must exist an assignment of times that connects a constant fraction of all pairs in the strongly temporalisable and symmetric case, that is, when the set of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. Keywords:edge labeling edge scheduled network network optimisation temporal graph temporal path temporal reachability time assignment
Complete list of metadata

https://hal.inria.fr/hal-03430099
Contributor : Laurent Viennot Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2021 - 9:31:34 AM
Last modification on : Tuesday, September 6, 2022 - 1:27:01 PM
Long-term archiving on: : Thursday, February 17, 2022 - 6:14:23 PM

Files

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03430099, version 1
  • ARXIV : 2111.08328

Collections

Citation

Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot. On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation. 2021. ⟨hal-03430099⟩

Share

Metrics

Record views

11

Files downloads

27