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.SAND.2022.15
URN: urn:nbn:de:0030-drops-159570
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15957/
Go to the corresponding LIPIcs Volume Portal

Erlebach, Thomas ; Spooner, Jakob T.

Parameterized Temporal Exploration Problems

pdf-format:
LIPIcs-SAND-2022-15.pdf (0.8 MB)

Abstract

In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph ? admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices. Formally, a temporal graph is a sequence ? = ⟨ G₁,..., G_L⟩ of graphs with V(G_t) = V(G) and E(G_t) ⊆ E(G) for all t ∈ [L] and some underlying graph G, and a temporal walk is a time-respecting sequence of edge-traversals. For the strict variant, in which edges must be traversed in strictly increasing timesteps, we give FPT algorithms for the problem of finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for the problem of finding a temporal walk that visits at least k distinct vertices in V, parameterized by k. For the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep, we parameterize by the lifetime L of the input graph and provide an FPT algorithm for the temporal exploration problem. We also give additional FPT or W[2]-hardness results for further problem variants.

BibTeX - Entry

@InProceedings{erlebach_et_al:LIPIcs.SAND.2022.15,
  author =	{Erlebach, Thomas and Spooner, Jakob T.},
  title =	{{Parameterized Temporal Exploration Problems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15957},
  URN =		{urn:nbn:de:0030-drops-159570},
  doi =		{10.4230/LIPIcs.SAND.2022.15},
  annote =	{Keywords: Temporal graphs, fixed-parameter tractability, parameterized complexity}
}

Keywords: Temporal graphs, fixed-parameter tractability, parameterized complexity
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

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