DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.122

Maximizing Reachability via Shifting of Temporal Paths

Authors: Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, and Georg Tennigkeit

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We examine the problem of maximizing the reachability of a given source in temporal graphs that are given as the union of 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, and the total budget b, where 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 and b, and (2) when parameterized by k, and b is unlimited. In almost every other case, e.g., parameterized by a single parameter or parameterized by k, while having a bound on b, we establish intractability lower bounds that are matched by XP algorithms.

Cite as

Argyrios Deligkas, Michelle Döring, Eduard Eiben, George Skretas, and Georg Tennigkeit. Maximizing Reachability via Shifting of Temporal Paths. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 122:1-122:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.ESA.2026.122,
  author =	{Deligkas, Argyrios and D\"{o}ring, Michelle and Eiben, Eduard and Skretas, George and Tennigkeit, Georg},
  title =	{{Maximizing Reachability via Shifting of Temporal Paths}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{122:1--122:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.122},
  URN =		{urn:nbn:de:0030-drops-272580},
  doi =		{10.4230/LIPIcs.ESA.2026.122},
  annote =	{Keywords: temporal graphs, temporal path number, path graph, reachability, train system, network optimization, parameterized complexity}
}

Search Results

Documents authored by Tennigkeit, Georg

Maximizing Reachability via Shifting of Temporal Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message