1 Search Results for "Schubert, Carsten"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.43
Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs

Authors: Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
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. One of our main technical results (employing so-called representative sets known from non-temporal settings) is that dissimilarity allows for fixed-parameter 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).
Cite as

Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche. Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.ISAAC.2020.43,
  author =	{Fluschnik, Till and Niedermeier, Rolf and Schubert, Carsten and Zschoche, Philipp},
  title =	{{Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.43},
  URN =		{urn:nbn:de:0030-drops-133879},
  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}
}
  • Refine by Author
  • 1 Fluschnik, Till
  • 1 Niedermeier, Rolf
  • 1 Schubert, Carsten
  • 1 Zschoche, Philipp

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Temporal graphs
  • 1 consecutive dissimilarity
  • 1 consecutive similarity
  • 1 kernelization
  • 1 parameterized complexity
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact