2026-07-23T05:31:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15957 2024-03-06T10:56:30Z ddc:004 open_access

Parameterized Temporal Exploration Problems Erlebach, Thomas Spooner, Jakob T. Temporal graphs fixed-parameter tractability parameterized complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Erlebach and Jakob T. Spooner 2022 Is Part Of LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2022.15 urn:nbn:de:0030-drops-159570 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.15 eng https://creativecommons.org/licenses/by/4.0/legalcode