  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. 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
leafs, and eventually returns back to the center. We initiate 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 every 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 present here a collection of results
establishing the computational complexity of these two problems. On the one
hand, we show that both MaxStarExp(2) and StarExp(3) can be efficiently solved
in O(n log n) time on a temporal star with n vertices. On the other hand, we
show that, for every k >= 6, StarExp(k) is NP-complete and MaxStarExp(k) is
APX-hard, and thus it does not admit a PTAS, unless P = NP. The latter result
is complemented by a polynomial-time 2-approximation algorithm for
MaxStarExp(k), for every k, thus proving that MaxStarExp(k) is APX-complete.
Finally, we give a partial characterization of the classes of temporal stars
with random labels which are, asymptotically almost surely, yes-instances and
no-instances for StarExp(k) respectively.
