Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks. Issue 2 (30th August 2022)

• Record Type: Journal Article
• Authors: Brunelli, Filippo; Crescenzi, Pierluigi; Viennot, Laurent
• Is Part Of: Networks. Volume 81:Issue 2(2023)
• Page Start: 177
• Page End: 203
• Publication Date: 2022-08-30
• Subjects: edge labeling -- edge scheduled network -- network optimization -- temporal graph -- temporal path -- temporal reachability -- time assignment; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22123
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: 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 optimization 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 in order to maximize 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 appearance time of all its edges. We call such a starting time assignment a trip temporalization. We obtain several results about the complexity of maximizing reachability via trip temporalization. Among them, we show that maximizing reachability via trip temporalization is hard to approximate within a factor n / 12 $$ \sqrt{n}/12 $$ in an n $$ n $$ ‐vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalization connecting them. On the positive side, we show that there must exist a trip temporalization 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.