DROPS

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}
}

Document

DOI: 10.4230/LIPIcs.FUN.2018.30

The Complexity of Escaping Labyrinths and Enchanted Forests

Authors: Florian D. Schwahn and Clemens Thielen

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract

The board games The aMAZEing Labyrinth (or simply Labyrinth for short) and Enchanted Forest published by Ravensburger are seemingly simple family games. In Labyrinth, the players move though a labyrinth in order to collect specific items. To do so, they shift the tiles making up the labyrinth in order to open up new paths (and, at the same time, close paths for their opponents). We show that, even without any opponents, determining a shortest path (i.e., a path using the minimum possible number of turns) to the next desired item in the labyrinth is strongly NP-hard. Moreover, we show that, when competing with another player, deciding whether there exists a strategy that guarantees to reach one's next item faster than one's opponent is PSPACE-hard. In Enchanted Forest, items are hidden under specific trees and the objective of the players is to report their locations to the king in his castle. Movements are performed by rolling two dice, resulting in two numbers of fields one has to move, where each of the two movements must be executed consecutively in one direction (but the player can choose the order in which the two movements are performed). Here, we provide an efficient polynomial-time algorithm for computing a shortest path between two fields on the board for a given sequence of die rolls, which also has implications for the complexity of problems the players face in the game when future die rolls are unknown.

Cite as

Florian D. Schwahn and Clemens Thielen. The Complexity of Escaping Labyrinths and Enchanted Forests. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{schwahn_et_al:LIPIcs.FUN.2018.30,
  author =	{Schwahn, Florian D. and Thielen, Clemens},
  title =	{{The Complexity of Escaping Labyrinths and Enchanted Forests}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.30},
  URN =		{urn:nbn:de:0030-drops-88210},
  doi =		{10.4230/LIPIcs.FUN.2018.30},
  annote =	{Keywords: board games, combinatorial game theory, computational complexity}
}

Search Results

Documents authored by Thielen, Clemens

Complexity of the Temporal Shortest Path Interdiction Problem

Abstract

Cite as

The Complexity of Escaping Labyrinths and Enchanted Forests

Abstract

Cite as

Thanks for your feedback!

Could not send message