Fluschnik, Till ;
Niedermeier, Rolf ;
Schubert, Carsten ;
Zschoche, Philipp
Multistage st Path: Confronting Similarity with Dissimilarity in Temporal Graphs
Abstract
Addressing a quest by Gupta et al. [ICALP'14], we provide a first, comprehensive study of finding a short st path in the multistage graph model, referred to as the Multistage st Path problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short st paths in each graph ("snapshot") such that in the found path sequence the consecutive st paths are "similar". We measure similarity by the size of the symmetric difference of either the vertex set (vertexsimilarity) or the edge set (edgesimilarity) of any two consecutive paths. We prove that these two variants of Multistage st Path are already NPhard 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 edgesimilarity, we prove parameterized hardness (W[1]hardness) regarding the parameter path length (solution size) for both variants, vertex and edgesimilarity. As a further conceptual study, we then modify the multistage model by asking for dissimilar consecutive paths. One of our main technical results (employing socalled representative sets known from nontemporal settings) is that dissimilarity allows for fixedparameter tractability for the parameter solution size, contrasting the W[1]hardness of the corresponding similarity case. We also provide partially positive results concerning efficient and effective data reduction (kernelization).
BibTeX  Entry
@InProceedings{fluschnik_et_al:LIPIcs:2020:13387,
author = {Till Fluschnik and Rolf Niedermeier and Carsten Schubert and Philipp Zschoche},
title = {{Multistage st Path: Confronting Similarity with Dissimilarity in Temporal Graphs}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {43:143:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13387},
URN = {urn:nbn:de:0030drops133879},
doi = {10.4230/LIPIcs.ISAAC.2020.43},
annote = {Keywords: Temporal graphs, shortest paths, consecutive similarity, consecutive dissimilarity, parameterized complexity, kernelization, representative sets in temporal graphs}
}
04.12.2020
Keywords: 

Temporal graphs, shortest paths, consecutive similarity, consecutive dissimilarity, parameterized complexity, kernelization, representative sets in temporal graphs 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 