DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2026.17

Label Correcting Algorithms for the Multiobjective Temporal Shortest Path Problem

Authors: Edina Marica, Clemens Thielen, and Alina Wittmann

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract

Given a directed, discrete-time temporal graph G = (V,R), a start node s ∈ V, and p ≥ 1 objectives, the single-source multiobjective temporal shortest path problem asks, for each v ∈ V, for the set of nondominated images of temporal s-v-paths together with a corresponding efficient path for each image. A recent general label setting algorithm for this problem relies on two properties of the objectives-monotonicity and isotonicity. Monotonicity generalizes the nonnegativity assumption required by label setting methods for the classical additive single-objective shortest path problem on static graphs, while isotonicity ensures that the order of the objective values of two paths is preserved when both are extended by the same arc. In this paper, we study the problem without assuming monotonicity and/or isotonicity. A key difficulty in this setting is that zero-duration temporal cycles may need to be traversed an arbitrary finite number of times to generate all nondominated images. This motivates the study of a restricted problem variant in which a maximum admissible path length K is imposed, and only paths containing at most K arcs are considered. We develop general label correcting algorithms for this setting and establish several sufficient conditions under which such a bound is not required, implying that the algorithms compute all nondominated images.

Cite as

Edina Marica, Clemens Thielen, and Alina Wittmann. Label Correcting Algorithms for the Multiobjective Temporal Shortest Path Problem. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{marica_et_al:LIPIcs.SAND.2026.17,
  author =	{Marica, Edina and Thielen, Clemens and Wittmann, Alina},
  title =	{{Label Correcting Algorithms for the Multiobjective Temporal Shortest Path Problem}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.17},
  URN =		{urn:nbn:de:0030-drops-262518},
  doi =		{10.4230/LIPIcs.SAND.2026.17},
  annote =	{Keywords: temporal graphs, multiobjective optimization, shortest paths, label correcting algorithm}
}

Document

DOI: 10.4230/LIPIcs.SAND.2023.9

Complexity of the Temporal Shortest Path Interdiction Problem

Authors: Jan Boeckmann, Clemens Thielen, and Alina Wittmann

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract

In the shortest path interdiction problem, an interdictor aims to remove arcs of total cost at most a given budget from a directed graph with given arc costs and traversal times such that the length of a shortest s-t-path is maximized. For static graphs, this problem is known to be strongly NP-hard, and it has received considerable attention in the literature. While the shortest path problem is one of the most fundamental and well-studied problems also for temporal graphs, the shortest path interdiction problem has not yet been formally studied on temporal graphs, where common definitions of a "shortest path" include: latest start path (path with maximum start time), earliest arrival path (path with minimum arrival time), shortest duration path (path with minimum traveling time including waiting times at nodes), and shortest traversal path (path with minimum traveling time not including waiting times at nodes). In this paper, we analyze the complexity of the shortest path interdiction problem on temporal graphs with respect to all four definitions of a shortest path mentioned above. Even though the shortest path interdiction problem on static graphs is known to be strongly NP-hard, we show that the latest start and the earliest arrival path interdiction problems on temporal graphs are polynomial-time solvable. For the shortest duration and shortest traversal path interdiction problems, however, we show strong NP-hardness, but we obtain polynomial-time algorithms for these problems on extension-parallel temporal graphs.

Cite as

Jan Boeckmann, Clemens Thielen, and Alina Wittmann. Complexity of the Temporal Shortest Path Interdiction Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boeckmann_et_al:LIPIcs.SAND.2023.9,
  author =	{Boeckmann, Jan and Thielen, Clemens and Wittmann, Alina},
  title =	{{Complexity of the Temporal Shortest Path Interdiction Problem}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.9},
  URN =		{urn:nbn:de:0030-drops-179455},
  doi =		{10.4230/LIPIcs.SAND.2023.9},
  annote =	{Keywords: Temporal Graphs, Interdiction Problems, Complexity, Shortest Paths, Most Vital Arcs}
}

Search Results

Documents authored by Wittmann, Alina

Label Correcting Algorithms for the Multiobjective Temporal Shortest Path Problem

Abstract

Cite as

Complexity of the Temporal Shortest Path Interdiction Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message