Skip to main content

Research Repository

Advanced Search

The temporal explorer who returns to the base

Akrida, E.C.; Mertzios, G.B.; Spirakis, P.G.

The temporal explorer who returns to the base Thumbnail


Authors

P.G. Spirakis



Contributors

P Heggernes
Editor

Abstract

In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploration problem in a temporal star is to find a temporal walk which starts at the center of the star, visits all leaves, and eventually returns back to the center. We present here a systematic study of the computational complexity of this problem, depending on the number k of time-labels that every edge is allowed to have; that is, on the number k of time points where each edge can be present in the graph. To do so, we distinguish between the decision version STAREXP(k) , asking whether a complete exploration of the instance exists, and the maximization version MAXSTAREXP(k) of the problem, asking for an exploration schedule of the greatest possible number of edges in the star. We fully characterize MAXSTAREXP(k) and show a dichotomy in terms of its complexity: on one hand, we show that for both k=2 and k=3 , it can be efficiently solved in O(nlogn) time; on the other hand, we show that it is APX-complete, for every k≥4 (does not admit a PTAS, unless P = NP, but admits a polynomial-time 1.582-approximation algorithm). We also partially characterize STAREXP(k) in terms of complexity: we show that it can be efficiently solved in O(nlogn) time for k∈{2,3} (as a corollary of the solution to MAXSTAREXP(k) , for k∈{2,3} ), but is NP-complete, for every k≥6 .

Citation

Akrida, E., Mertzios, G., & Spirakis, P. (2019). The temporal explorer who returns to the base. In P. Heggernes (Ed.), Algorithms and Complexity (CIAC 2019); 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019 ; proceedings (13-24). https://doi.org/10.1007/978-3-030-17402-6_2

Conference Name 11th International Conference on Algorithms and Complexity (CIAC 2019)
Conference Location Rome, Italy
Acceptance Date Dec 21, 2018
Online Publication Date Apr 6, 2019
Publication Date Apr 6, 2019
Deposit Date Jan 10, 2019
Publicly Available Date Mar 29, 2024
Pages 13-24
Series Title Lecture notes in computer science
Series Number 11485
Series ISSN 0302-9743,1611-3349
Book Title Algorithms and Complexity (CIAC 2019); 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019 ; proceedings.
ISBN 9783030174019
DOI https://doi.org/10.1007/978-3-030-17402-6_2
Public URL https://durham-repository.worktribe.com/output/1144950
Related Public URLs https://arxiv.org/abs/1805.04713

Files

Accepted Conference Proceeding (634 Kb)
PDF

Copyright Statement
This is a post-peer-review, pre-copyedit version of an article published in Algorithms and Complexity (CIAC 2019); 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019 ; proceedings. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-17402-6_2





You might also like



Downloadable Citations