Document Open Access Logo

Finding Temporal Paths Under Waiting Time Constraints

Authors Arnaud Casteigts , Anne-Sophie Himmel , Hendrik Molter , Philipp Zschoche

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.30.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Arnaud Casteigts
  • LaBRI, Université de Bordeaux, CNRS, Bordeaux INP, France
Anne-Sophie Himmel
  • Technische Universität Berlin, Algorithmics and Computational Complexity, Germany
Hendrik Molter
  • Technische Universität Berlin, Algorithmics and Computational Complexity, Germany
Philipp Zschoche
  • Technische Universität Berlin, Algorithmics and Computational Complexity, Germany

Funding

  • Casteigts, Arnaud: Supported by the ANR, project ESTATE (ANR-16-CE25-0009-03).
  • Himmel, Anne-Sophie: Supported by the DFG, project FPTinP (NI 369/16).
  • Molter, Hendrik: Supported by the DFG, project MATE (NI 369/17).

Cite As Get BibTex

Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding Temporal Paths Under Waiting Time Constraints. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.30

Abstract

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps.
We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance.
While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Temporal graphs
  • disease spreading
  • waiting-time policies
  • restless temporal paths
  • timed feedback vertex set
  • NP-hard problems
  • parameterized algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized complexity of conflict-free matchings and paths. Algorithmica, pages 1-27, 2020. Google Scholar
  2. Eleni C. Akrida, Jurek Czyzowicz, Leszek Gąsieniec, Łukasz Kuszner, and Paul G. Spirakis. Temporal flows in temporal networks. Journal of Computer and System Sciences, 103:46-60, 2019. Google Scholar
  3. Eleni C Akrida, Leszek Gąsieniec, George B Mertzios, and Paul G Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3):907-944, 2017. Google Scholar
  4. Eleni C. Akrida, George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis, and Viktor Zamaraev. How fast can we reach a target vertex in stochastic temporal graphs? Journal of Computer and System Sciences, 114:65-83, 2020. Google Scholar
  5. Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP '16), pages 149:1-149:14, 2016. Google Scholar
  6. Albert-László Barabási. Network Science. Cambridge University Press, 2016. Google Scholar
  7. Matthias Bentert, René van Bevern, and Rolf Niedermeier. Inductive k-independent graphs and c-colorable subgraphs in scheduling: a review. Journal of Scheduling, 22(1):3-20, 2019. Google Scholar
  8. Kenneth A Berman. Vulnerability of scheduled networks and a generalization of Menger’s theorem. Networks: An International Journal, 28(3):125-134, 1996. Google Scholar
  9. René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5):449-469, 2015. Google Scholar
  10. Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In International Conference on Ad-Hoc Networks and Wireless, pages 259-270. Springer, 2003. Google Scholar
  11. B.-M. Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(02):267-285, 2003. Google Scholar
  12. Arnaud Casteigts, Paola Flocchini, Emmanuel Godard, Nicola Santoro, and Masafumi Yamashita. On the expressivity of time-varying graphs. Theoretical Computer Science, 590:27-37, 2015. Google Scholar
  13. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  14. Arnaud Casteigts, Joseph Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP '19), volume 132 of LIPIcs, pages 134:1-134:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019. Google Scholar
  15. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  16. Reinhard Diestel. Graph Theory, 5th Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2016. Google Scholar
  17. Rodney G Downey and Michael R Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  18. Ken TD Eames and Matt J Keeling. Contact tracing and disease control. Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(1533):2565-2571, 2003. Google Scholar
  19. Jessica Enright, Kitty Meeks, George Mertzios, and Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS '19), volume 138 of LIPIcs, pages 57:1-57:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019. Google Scholar
  20. Luca Ferretti, Chris Wymant, Michelle Kendall, Lele Zhao, Anel Nurtay, Lucie Abeler-Dörner, Michael Parker, David Bonsall, and Christophe Fraser. Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing. Science, 2020. Google Scholar
  21. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197-218, 2020. Google Scholar
  22. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM, 63(4):29:1-29:60, 2016. Google Scholar
  23. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative families of product families. ACM Transactions on Algorithms, 13(3):36:1-36:29, 2017. Google Scholar
  24. Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111-121, 1980. Google Scholar
  25. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  26. Roman Haag, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Feedback edge sets in temporal graphs. In Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '20), Lecture Notes in Computer Science. Springer, 2020. Accepted for publication. Google Scholar
  27. Anne-Sophie Himmel, Matthias Bentert, André Nichterlein, and Rolf Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. In Proceedings of the 8th International Conference on Complex Networks and their Applications, volume 882 of SCI, pages 494-506. Springer, 2019. Google Scholar
  28. Petter Holme. Modern temporal network theory: a colloquium. The European Physical Journal B, 88(9):234, 2015. Google Scholar
  29. Petter Holme. Temporal network structures controlling disease spreading. Physical Review E, 94.2:022305, 2016. Google Scholar
  30. Petter Holme and Jari Saramäki (eds.). Temporal Network Theory. Springer, 2019. Google Scholar
  31. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  32. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  33. Richard M Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972. Google Scholar
  34. David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4):820-842, 2002. Google Scholar
  35. William Ogilvy Kermack and Anderson G McKendrick. A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society of London, Series A., 115(772):700-721, 1927. Google Scholar
  36. Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8(1):61, 2018. Google Scholar
  37. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. ACM Trans. Algorithms, 14(2):14:1-14:20, 2018. Google Scholar
  38. Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471-4479, 2009. Google Scholar
  39. George B Mertzios, Othon Michail, and Paul G Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4):1416-1449, 2019. Google Scholar
  40. Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239-280, 2016. Google Scholar
  41. Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: Graphs, Structures, and Algorithms. Springer, 2012. Google Scholar
  42. Mark E J Newman. Networks. Oxford University Press, 2018. Google Scholar
  43. James G. Oxley. Matroid Theory. Oxford University Press, 1992. Google Scholar
  44. Raj Kumar Pan and Jari Saramäki. Path lengths, correlations, and centrality in temporal networks. Physical Review E, 84(1):016105, 2011. Google Scholar
  45. Manuel Sorge and Mathias Weller et al. The graph parameter hierarchy, 2018, 2020. URL: https://manyu.pro/assets/parameter-hierarchy.pdf.
  46. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. Google Scholar
  47. Ryan Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. Google Scholar
  48. H. Wu, J. Cheng, Y. Ke, S. Huang, Y. Huang, and H. Wu. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering, 28(11):2927-2942, 2016. Google Scholar
  49. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The complexity of finding separators in temporal graphs. Journal of Computer and System Sciences, 107:72-92, 2020. Google Scholar
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 About DROPS Imprint Privacy Contact