Maximising reachability via walk temporalisation
In a temporal graph, each edge appears and can be traversed at specific points in time. In such a graph, temporal reachability of one node from another is naturally captured by the existence of a temporal path where edges appear in chronological order. Inspired by the optimisation of bus/metro/tramway schedules in a public transport network, we consider the problem of turning a collection of walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. Each trip represents the trajectory of a vehicle and its edges must be scheduled one right after another. Setting a starting time to the trip thus forces the appearing time of all its edges. We call such a starting time assignment a trip temporalisation. We obtain several results about the complexity of maximising reachability via trip temporalisation. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order.
Bio of the speaker: Filippo Brunelli received his Master degree in mathematics from the University of Pisa in 2019. He is currently a third year PhD student enrolled at Inria Paris and hosted at IRIF (Insitut de Recherche en Informatique Fondamentale) laboratory in Paris, under the supervision of Laurent Viennot and Pierluigi Crescenzi. His main research interests include temporal graphs and algorithms for transport networks.
Location: in-person at FBK – Room 211 – North Building Second Floor (limited access, subject to seating availability).