  Addressing a quest by Gupta et al. [ICALP'14], we provide a first,
comprehensive study of finding a short s-t path in the multistage graph model,
referred to as the Multistage s-t Path problem. Herein, given a sequence of
graphs over the same vertex set but changing edge sets, the task is to find
short s-t paths in each graph ("snapshot") such that in the found path sequence
the consecutive s-t paths are "similar". We measure similarity by the size of
the symmetric difference of either the vertex set (vertex-similarity) or the
edge set (edge-similarity) of any two consecutive paths. We prove that these
two variants of Multistage s-t Path are already NP-hard for an input sequence
of only two graphs and maximum vertex degree four. Motivated by this fact and
natural applications of this scenario e.g. in traffic route planning, we
perform a parameterized complexity analysis. Among other results, for both
variants, vertex- and edge-similarity, we prove parameterized hardness
(W[1]-hardness) regarding the parameter path length (solution size) for both
variants, vertex- and edge-similarity. As a further conceptual study, we then
modify the multistage model by asking for dissimilar consecutive paths. As one
of the main technical results (employing so-called representative sets known
from non-temporal settings), we prove that dissimilarity allows for
fixed-parameter tractability for the parameter solution size, contrasting our
W[1]-hardness proof of the corresponding similarity case. We also provide
partially positive results concerning efficient and effective data reduction
(kernelization).
