Maximizing Reachability via Shifting of Temporal Paths
Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, Georg Tennigkeit · 2026
Read Maximizing Reachability via Shifting of Temporal Paths by Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, Georg Tennigkeit (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11873.txt.
Introduction
Argyrios Deligkas and four colleagues study how to boost reach in time graphs formed by k time paths, such as train networks. They allow shifting edge timing labels earlier or later while keeping each path's time flow. The problem stays easy when measured by both path count and shift budget, and when measured by path count alone with open budget. Nearly every other setup proves hard, with matching XP methods.
Catalog record
| CREATOR | Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, Georg Tennigkeit |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111649 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11873
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Maximizing Reachability via Shifting of Temporal Paths Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, Georg Tennigkeit Abstract We examine the problem of maximizing the reachability of a given source in temporal graphs that are given as the union of k k temporal paths, i.e., every given path is a sequence of edges with strictly increasing labels that denote availability in time. This type of temporal graphs represent train networks. We consider shifting operations on the labels of the paths that maintain their temporal continuity. This means that we can move the availability of a temporal edge later or earlier in time, and propagate the shifts to all other affected edges of the path in order to preserve its temporal connectivity. We study the parameterized complexity of the problem with respect to the number of paths k k , and the total budget b b , where b b is the maximum number of shifts we are allowed to perform. Our results reveal that fixed parameter tractability can be achieved (1) when parameterized both by k k and b b , and (2) when parameterized by k k , and b b is unconstrained. In almost every other case, e.g., parameterized by a single parameter or parameterized by k k , while having a bound on b b , we establish intractability lower bounds that are matched by XP algorithms. Royal Holloway, University of London, Egham, United Kingdom and https://sites.google.com/view/deligkas/home [email protected] https://orcid.org/0000-0002-6513-6748 EPSRC Grant EP/X039862/1 “NAfANE: New Approaches for Approximate Nash Equilibria” Hasso Plattner Institute, University of Potsdam, Potsdam, Germany and https://www.notion.so/Michelle-D-ring-1dd43d6e8b7c800eadbdd32d73e21b72?pvs=25 [email protected] https://orcid.org/0000-0001-7737-3903 HPI Research School on Foundations of AI (FAI) Royal Holloway, University of London, Egham, United Kingdom and https://pure.royalholloway.ac.uk/en/persons/eduard-eiben [email protected] https://orcid.org/0000-0003-2628-3435 Hasso Plattner Institute, University of Potsdam, Potsdam, Germany [email protected] https://orcid.org/0000-0003-2514-8004 Hasso Plattner Institute, University of Potsdam, Potsdam, Germany [email protected] https://orcid.org/0000-0003-0734-0684 HPI Research School on Foundations of AI (FAI) \declaretheoremstyle [ headfont= , headformat= \lozenge \NAME \NOTE , headpunct=., notefont=, bodyfont= , spaceabove=6pt, spacebelow=6pt ]cleancons \declaretheorem [ numbered=no, name=Construction, qed= \lozenge ]leconstruction ccs Mathematics of computing Graph theory ccs Theory of computation Graph algorithms analysis ccs Theory of computation Fixed parameter tractability keywords temporal graphs, temporal path number, path graph, reachability, train system, network optimization, parameterized complexity † † runningauthor: A. Deligkas, M. Döring, E. Eiben, G. Skretas and G. Tennigkeit † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Probably the simplest way to describe the problem of maximizing reachability on a temporal graph is via a train network. We are given the routes and corresponding timings for each train, along with a specific station s . The question is, how should we modify the network such that s can reach as many other stations as possible? Formally, in a temporal graph, every edge has a set of labels that correspond to the specific timesteps at which the edge can be used. The modifications of the temporal graph proposed in the past ranged from the addition of (non-existing) edges [ 1 ] and labels, to advancing or delaying , i.e., shifting , the labels of the edges [ 7 , 8 , 16 , 17 ] . In real-life networks, though, especially physical ones, it is almost impossible to add new edges. We cannot simply add one direct connection from Warsaw to L’Aquila because we have decided so. Hence, shifting seems a more suitable operation in applications. On the other hand, in certain scenarios, like train networks, delaying or advancing a temporal edge cannot happen in isolation. Trains pass through many different stations, and we cannot simply change the time at which it goes between two consecutive stations without potentially affecting the schedule of the entire train line. Imagine, for example, a train that leaves from A to B at 9:00 and from B to C at 10:00. We cannot delay the A - B connection to 12:00 and maintain the B - C connection at 10:00; the delay must propagate and connection B - C must be after 13:00. Thus, changes on a train line that occur due to shifting must propagate until feasibility on the corresponding temporal path is maintained. While maximum reachability via delaying operations had been studied in the past, the above-mentioned dimension of real life networks was overlooked. The goal of the paper is remedy this situation and resolve the (parameterized) complexity of maximum reachability of a vertex via shifting on temporal k -path graphs, i.e., temporal graphs that are defined by a collection of k temporal base-paths, denoted MaxReach-ShiftPath ( MR-SP for short). Problem 1.1 . MaxReach-ShiftPath ( MR-SP ) \Input A k -path graph \mathcal{G} , a budget b\in\mathbb{N} , and a vertex s . \Prob Find a sequence of shifting operations with a total cost of at most b , such that the number of vertices that s can reach in the resulting \mathcal{G}^{\prime} is maximized. More formally, a shifting operation either increases the time label of a specified edge (delaying) or decreases it (advancing). When delaying an edge, the delay propagates to subsequent edges on the unique containing base-path insofar as the labels remain strictly increasing. Likewise, advancing an edge propagates to preceding edges on the containing base-path. If there was any waiting time between edges in the base-path, it reduces the propagating shift, as if the delayed train can make up for its delay by driving faster on the connection, or waiting less at the station. The cost of one shifting operation is equal to the absolute value by which the specified edge is modified, while propagated changes do not count towards the cost. This reflects that the budget measures only the active intervention by the operator, namely how much a single departure is intentionally rescheduled. The resulting propagation along the same base-path is then a forced consequence of preserving a feasible timetable for that line, rather than an additional independent modification. Figure 1 demonstrates an instance of MR-SP alongside a solution. Figure 1: An example instance of MR-SP on a temporal 6-path graph, whose base-paths are depicted with different colours, along with a sequence of operations that allows s to reach all vertices for a cost of 6. Gray vertices are reached by s . 1.1 Our Contribution We begin our investigation by establishing some observations and deriving structural properties of optimal solutions in k -path graphs that help us design our algorithms. The most fundamental observation, that our algorithms heavily exploit, is the fact that in any k -path graph if vertex u reaches vertex v , then there is a temporal path from u to v that uses at most one contiguous segment from each base-path. This implies that there exists an optimal solution where each base-path switches to a different base-path at most once. This in turn implies the existence of a switch-path-tree , denoted \mathsf{SPT} . This is a directed tree, rooted at