License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.55
URN: urn:nbn:de:0030-drops-177077
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17707/
Go to the corresponding LIPIcs Volume Portal

Zschoche, Philipp

Restless Temporal Path Parameterized Above Lower Bounds

pdf-format:
LIPIcs-STACS-2023-55.pdf (0.8 MB)

Abstract

Reachability questions are one of the most fundamental algorithmic primitives in temporal graphs - graphs whose edge set changes over discrete time steps. A core problem here is the NP-hard Short Restless Temporal Path: given a temporal graph G, two distinct vertices s and z, and two numbers δ and k, is there a δ-restless temporal s-z path of length at most k? A temporal path is a path whose edges appear in chronological order and a temporal path is δ-restless if two consecutive path edges appear at most δ time steps apart from each other. Among others, this problem has applications in neuroscience and epidemiology. While Short Restless Temporal Path is known to be computationally hard, e.g., it is NP-hard even if the temporal graph consists of three discrete time steps and it is W[1]-hard when parameterized by the feedback vertex number of the underlying graph, it is fixed-parameter tractable when parameterized by the path length k. We improve on this by showing that Short Restless Temporal Path can be solved in (randomized) 4^(k-d)|G|^O(1) time, where d is the minimum length of a temporal s-z path.

BibTeX - Entry

@InProceedings{zschoche:LIPIcs.STACS.2023.55,
  author =	{Zschoche, Philipp},
  title =	{{Restless Temporal Path Parameterized Above Lower Bounds}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17707},
  URN =		{urn:nbn:de:0030-drops-177077},
  doi =		{10.4230/LIPIcs.STACS.2023.55},
  annote =	{Keywords: temporal graphs, FPT, above-lower-bound parameterization}
}

Keywords: temporal graphs, FPT, above-lower-bound parameterization
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI