A temporal graph $G$ is a sequence of graphs $G_1, G_2, \ldots, G_t$ on the same vertex set. In this talk, we are interested in the analogue of the Travelling Salesman Problem for temporal graphs. It is referred to in the literature as the Temporal Exploration Problem, and asks for the minimum length of an exploration of the graph, that is, a sequence of vertices such that at each time step $t$, one either stays at the same vertex or moves along a single edge of $G_t$.

One natural and still open case is when each graph $G_t$ is connected and has bounded maximum degree. We present a short proof that any such graph admits an exploration in $O(n^{3/2}\sqrt{\log n})$ time steps. In fact, we deduce this result from a more general statement by introducing the notion of average temporal maximum degree. This more general statement improves the previous best bounds, under a unified approach, for several studied exploration problems.

This is based on joint work with Carla Groenland, Lukas Michel and Clément Rambaud.

In the first part of the talk, I will present an overview of recent advances in the description of diffusion-reaction processes and their first-passage statistics, with the special emphasis on the role of the boundary local time and related spectral tools. The second part of the talk will illustrate the use of these tools for the analysis of boundary-catalytic branching processes. These processes describe a broad class of natural phenomena where the population of diffusing particles grows due to their spontaneous binary branching (e.g., division, fission, or splitting) on a catalytic boundary located in a complex environment. We investigate the possibility of the geometric control of the population growth by compensating the proliferation of particles due to catalytic branching events by their absorptions in the bulk or on boundary absorbing regions. We identify an appropriate Steklov spectral problem to obtain the phase diagram of this out-of-equilibrium stochastic process. The principal eigenvalue determines the critical line that separates an exponential growth of the population from its extinction. In other words, we establish a powerful tool for calculating the optimal absorption rate that equilibrates the opposite effects of branching and absorption events and thus results in steady-state behavior of this diffusion-reaction system. Moreover, we show the existence of a critical catalytic rate above which no compensation is possible, so that the population cannot be controlled and keeps growing exponentially. The proposed framework opens promising perspectives for better understanding, modeling, and control of various boundary-catalytic branching processes, with applications in physics, chemistry, and life sciences.