Skip to main content

Research Repository

Advanced Search

Parameterized temporal exploration problems

Erlebach, Thomas; Spooner, Jakob T.

Parameterized temporal exploration problems Thumbnail


Authors

Jakob T. Spooner



Contributors

James Aspnes
Editor

Othon Michail
Editor

Abstract

In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph G 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 = hG1, ..., GLi of graphs with V (Gt) = V (G) and E(Gt) ⊆ 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.

Citation

Erlebach, T., & Spooner, J. T. (2022). Parameterized temporal exploration problems. In J. Aspnes, & O. Michail (Eds.), . https://doi.org/10.4230/lipics.sand.2022.15

Conference Name 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Conference Location Virtual Conference
Start Date Mar 28, 2022
End Date Mar 30, 2022
Acceptance Date Jan 31, 2022
Online Publication Date Apr 29, 2022
Publication Date 2022
Deposit Date Feb 27, 2022
Publicly Available Date May 11, 2022
Publisher Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume 221
Pages 15:1-15:17
Series Title LIPIcs
DOI https://doi.org/10.4230/lipics.sand.2022.15
Public URL https://durham-repository.worktribe.com/output/1137637

Files






You might also like



Downloadable Citations