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



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 timerespecting sequence of edge-traversals. We consider both the strict variant, in which edges must be traversed in strictly increasing timesteps, and the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep. For both variants, 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 (G), parameterized by k. We also show W[2]-hardness for a set version of the temporal exploration problem for both variants. For the non-strict variant, we give an FPT algorithm for the temporal exploration problem parameterized by the lifetime of the input graph, and we show that the temporal exploration problem can be solved in polynomial time if the graph in each timestep has at most two connected components.

Citation

Erlebach, T., & Spooner, J. T. (2023). Parameterized temporal exploration problems. Journal of Computer and System Sciences, 135, 73-88. https://doi.org/10.1016/j.jcss.2023.01.003

Journal Article Type Article
Acceptance Date Jan 19, 2023
Online Publication Date Mar 6, 2023
Publication Date 2023
Deposit Date Jan 23, 2023
Publicly Available Date Jan 30, 2023
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Electronic ISSN 1090-2724
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 135
Pages 73-88
DOI https://doi.org/10.1016/j.jcss.2023.01.003
Public URL https://durham-repository.worktribe.com/output/1184842

Files







You might also like



Downloadable Citations