1 Search Results for "Himmel, Anne-Sophie"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.30
Finding Temporal Paths Under Waiting Time Constraints

Authors: Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.
Cite as

Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding Temporal Paths Under Waiting Time Constraints. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.ISAAC.2020.30,
  author =	{Casteigts, Arnaud and Himmel, Anne-Sophie and Molter, Hendrik and Zschoche, Philipp},
  title =	{{Finding Temporal Paths Under Waiting Time Constraints}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.30},
  URN =		{urn:nbn:de:0030-drops-133745},
  doi =		{10.4230/LIPIcs.ISAAC.2020.30},
  annote =	{Keywords: Temporal graphs, disease spreading, waiting-time policies, restless temporal paths, timed feedback vertex set, NP-hard problems, parameterized algorithms}
}
  • Refine by Author
  • 1 Casteigts, Arnaud
  • 1 Himmel, Anne-Sophie
  • 1 Molter, Hendrik
  • 1 Zschoche, Philipp

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 NP-hard problems
  • 1 Temporal graphs
  • 1 disease spreading
  • 1 parameterized algorithms
  • 1 restless temporal paths
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact