Document Open Access Logo

Complexity of the Temporal Shortest Path Interdiction Problem

Authors Jan Boeckmann , Clemens Thielen , Alina Wittmann

PDF
Thumbnail PDF

File

LIPIcs.SAND.2023.9.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Author Details

Jan Boeckmann
  • TUM Campus Straubing for Biotechnology and Sustainability, Hochschule Weihenstephan-Triesdorf, Germany
Clemens Thielen
  • TUM Campus Straubing for Biotechnology and Sustainability, Hochschule Weihenstephan-Triesdorf, Germany
  • Department of Mathematics, School of Computation, Information and Technology, Technische Universität München, Germany
Alina Wittmann
  • Department of Mathematics, School of Computation, Information and Technology, Technische Universität München, Germany

Cite As Get BibTex

Jan Boeckmann, Clemens Thielen, and Alina Wittmann. Complexity of the Temporal Shortest Path Interdiction Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SAND.2023.9

Abstract

In the shortest path interdiction problem, an interdictor aims to remove arcs of total cost at most a given budget from a directed graph with given arc costs and traversal times such that the length of a shortest s-t-path is maximized. For static graphs, this problem is known to be strongly NP-hard, and it has received considerable attention in the literature.
While the shortest path problem is one of the most fundamental and well-studied problems also for temporal graphs, the shortest path interdiction problem has not yet been formally studied on temporal graphs, where common definitions of a "shortest path" include: latest start path (path with maximum start time), earliest arrival path (path with minimum arrival time), shortest duration path (path with minimum traveling time including waiting times at nodes), and shortest traversal path (path with minimum traveling time not including waiting times at nodes).
In this paper, we analyze the complexity of the shortest path interdiction problem on temporal graphs with respect to all four definitions of a shortest path mentioned above. Even though the shortest path interdiction problem on static graphs is known to be strongly NP-hard, we show that the latest start and the earliest arrival path interdiction problems on temporal graphs are polynomial-time solvable. For the shortest duration and shortest traversal path interdiction problems, however, we show strong NP-hardness, but we obtain polynomial-time algorithms for these problems on extension-parallel temporal graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Dynamic graph algorithms
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Temporal Graphs
  • Interdiction Problems
  • Complexity
  • Shortest Paths
  • Most Vital Arcs

Metrics

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

References

  1. E. C. Akrida, G. B. Mertzios, P. G. Spirakis, and V. Zamaraev. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107:108-123, 2020. URL: https://doi.org/10.1016/j.jcss.2019.08.002.
  2. M. O. Ball, B. L. Golden, and R. V. Vohra. Finding the most vital arcs in a network. Operations Research Letters, 8(2):73-76, 1989. URL: https://doi.org/10.1016/0167-6377(89)90003-5.
  3. A. Bar-Noy, S. Khuller, and B. Schieber. The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, University of Maryland, 1995. Google Scholar
  4. B. M. Behring, A. Rizzo, and M. Porfiri. How adherence to public health measures shapes epidemic spreading: A temporal network model. Chaos: An Interdisciplinary Journal of Nonlinear Science, 31(4):043115, 2021. URL: https://doi.org/10.1063/5.0041993.
  5. M. Bentert, A.-S. Himmel, A. Nichterlein, and R. Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. Applied Network Science, 5(1):73, 2020. URL: https://doi.org/10.1007/s41109-020-00311-0.
  6. C. Bentz. On the hardness of finding near-optimal multicuts in directed acyclic graphs. Theoretical Computer Science, 412(39):5325-5332, 2011. URL: https://doi.org/10.1016/j.tcs.2011.06.003.
  7. K. A. Berman. Vulnerability of scheduled networks and a generalization of Menger’s Theorem. Networks, 28(3):125-134, 1996. URL: https://doi.org/10.1002/(SICI)1097-0037(199610)28:3<125::AID-NET1>3.0.CO;2-P.
  8. J. Boeckmann and C. Thielen. A (B+1)-approximation for network flow interdiction with unit costs. Discrete Applied Mathematics (online first), pages 1-14, 2021. URL: https://doi.org/10.1016/j.dam.2021.07.008.
  9. F. Brunelli, P. Crescenzi, and L. Viennot. On computing Pareto optimal paths in weighted time-dependent networks. Information Processing Letters, 168:106086, 2021. URL: https://doi.org/10.1016/j.ipl.2020.106086.
  10. B. Bui-Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(2):267-285, 2003. URL: https://doi.org/10.1142/S0129054103001728.
  11. C. Burch, R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In D. L. Woodruff, editor, Network Interdiction and Stochastic Integer Programming, chapter 1, pages 51-68. Kluwer Academic Press, 2003. URL: https://doi.org/10.1007/0-306-48109-X_3.
  12. S. Busam, L. E. Schäfer, and S. Ruzika. The two player shortest path network interdiction problem, 2020. URL: https://arxiv.org/abs/2004.08338.
  13. A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. URL: https://doi.org/10.1080/17445760.2012.668546.
  14. A. Casteigts, A.-S. Himmel, H. Molter, and P. Zschoche. Finding temporal paths under waiting time constraints. Algorithmica, 83(9):2754-2802, 2021. URL: https://doi.org/10.1007/s00453-021-00831-w.
  15. S. R. Chestnut and R. Zenklusen. Hardness and approximation for network flow interdiction. Networks, 69(4):378-387, 2017. URL: https://doi.org/10.1002/net.21739.
  16. A. Deligkas and I. Potapov. Optimizing reachability sets in temporal graphs by delaying. Information and Computation, 285:104890, 2022. URL: https://doi.org/10.1016/j.ic.2022.104890.
  17. J. Enright, K. Meeks, G. B. Mertzios, and V. Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119:60-77, 2021. URL: https://doi.org/10.1016/j.jcss.2021.01.007.
  18. J. Enright, K. Meeks, and F. Skerman. Assigning times to minimise reachability in temporal graphs. Journal of Computer and System Sciences, 115:169-186, 2021. URL: https://doi.org/10.1016/j.jcss.2020.08.001.
  19. A. Epstein, M. Feldman, and Y. Mansour. Strong equilibrium in cost sharing connection games. In Proceedings of the 8th ACM Conference on Electronic Commerce (EC), pages 84-92, 2007. URL: https://doi.org/10.1145/1250910.1250924.
  20. T. Fluschnik, H. Molter, R. Niedermeier, M. Renken, and P. Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197-218, 2020. URL: https://doi.org/10.1016/j.tcs.2019.03.031.
  21. T. Holzmann and J.C. Smith. The shortest path interdiction problem with randomized interdiction strategies: Complexity and algorithms. Operations Research, 69(1):82-99, 2021. URL: https://doi.org/10.1287/opre.2020.2023.
  22. A. Ibiapina, R. Lopes, A. Marino, and A. Silva. Menger’s Theorem for temporal paths (not walks), 2022. URL: https://arxiv.org/abs/2206.15251.
  23. D. Kempke, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. In Proceedings of the 32nd ACM Symposium on the Theory of Computing (STOC), pages 504-513, 2000. Google Scholar
  24. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf, and J. Zhao. On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43(2):204-233, 2008. URL: https://doi.org/10.1007/s00224-007-9025-6.
  25. N. Maack, H. Molter, R. Niedermeier, and M. Renken. On finding separators in temporal split and permutation graphs. Journal of Computer and System Sciences, 135:1-14, 2023. URL: https://doi.org/10.1016/j.jcss.2023.01.004.
  26. O. Michail and P.G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.006.
  27. H. Molter. Classic Graph Problems Made Temporal - A Parameterized Complexity Analysis. PhD thesis, Technische Universität Berlin, 2020. Google Scholar
  28. H. Molter. The complexity of finding temporal separators under waiting time constraints. Information Processing Letters, 175:106229, 2022. URL: https://doi.org/10.1016/j.ipl.2021.106229.
  29. H. Molter, M. Renken, and P. Zschoche. Temporal reachability minimization: Delaying vs. deleting, 2021. URL: https://arxiv.org/abs/2102.10814.
  30. P. Mutzel and L. Oettershagen. On the enumeration of bicriteria temporal paths. In Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC), volume 11436 of Lecture Notes in Computer Science, pages 518-535, 2019. URL: https://doi.org/10.1007/978-3-030-14812-6_32.
  31. L. Oettershagen. Temporal Graph Algorithms. PhD thesis, Rheinische Friedrich-Wilhelms-Universität Bonn, 2022. Google Scholar
  32. J. B. Orlin. Minimum convex cost dynamic network flows. Mathematics of Operations Research, 9(2):190-207, 1984. URL: https://doi.org/10.1287/moor.9.2.190.
  33. C. Phillips. The network inhibition problem. In Proceedings of the 25th ACM Symposium on the Theory of Computing (STOC), pages 776-785, 1993. Google Scholar
  34. J. A. Sefair and J. C. Smith. Dynamic shortest-path interdiction. Networks, 68(4):315-330, 2016. URL: https://doi.org/10.1002/net.21712.
  35. J.C. Smith and Y. Song. A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3):797-811, 2020. URL: https://doi.org/10.1016/j.ejor.2019.06.024.
  36. J. Valdes, R. E. Tarjan, and E. L. Lawler. The recognition of series parallel digraphs. SIAM Journal on Computing, 11(2):298-313, 1982. URL: https://doi.org/10.1145/800135.804393.
  37. R. D. Wollmer. Removing arcs from a network. Operations Research, 12(6):934-940, 1964. URL: https://doi.org/10.1287/opre.12.6.934.
  38. 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. URL: https://doi.org/10.1109/TKDE.2016.2594065.
  39. P. Zschoche, T. Fluschnik, H. Molter, and R. Niedermeier. The complexity of finding small separators in temporal graphs. Journal of Computer and System Sciences, 107:72-92, 2020. URL: https://doi.org/10.1016/j.jcss.2019.07.006.
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