Parameterized temporal exploration problems

Erlebach, Thomas; Spooner, Jakob T.

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, March). Parameterized temporal exploration problems. Presented at 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), Virtual Conference

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
• 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