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 resulting 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 the two variants of Multistage s-t Path are already NP-hard for an input sequence of only two graphs  . 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,  we prove parameterized hardness (W[1]-hardness) regarding the size of the path sequence (solution size) for both variants, vertex- and edge-similarity. As a novel conceptual contribution , we then modify the multistage model by asking for dissimilar consecutive paths. As one of the main results , we prove that dissimilarity allows for fixed-parameter tractability for the parameter solution size, thereby contrasting our W[1]-hardness proof of the corresponding similarity case  .
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) .
R
resulting
found
R
the
these
A
and maximum vertex degree four
A
for both variants, vertex- and edge-similarity,
R
size of the path sequence
parameter path length
R
novel conceptual contribution
further conceptual study
R
results
technical results (employing so-called representative sets known from non-temporal settings)
D
thereby
A
. We also provide partially positive results concerning efficient and effective data reduction (kernelization)