Document Open Access Logo

Temporal Reachability Minimization: Delaying vs. Deleting

Authors Hendrik Molter , Malte Renken , Philipp Zschoche

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.76.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Hendrik Molter
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer Sheva, Israel
  • Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Malte Renken
  • Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Philipp Zschoche
  • Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany

Funding

  • Molter, Hendrik: Supported by the German Research Foundation (DFG), project MATE (NI 369/17), and by the Israeli Science Foundation (ISF), grant No. 1070/20. The main work was done while affiliated with TU Berlin.
  • Renken, Malte: Supported by the German Research Foundation (DFG), project MATE (NI 369/17).

Acknowledgements

This work was initiated at the research retreat of the Algorithmics and Computational Complexity group of TU Berlin in September 2020 in Zinnowitz.

Cite AsGet BibTex

Hendrik Molter, Malte Renken, and Philipp Zschoche. Temporal Reachability Minimization: Delaying vs. Deleting. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.76

Abstract

We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases or information flows. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and (2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Network flows
Keywords
  • Temporal Graphs
  • Temporal Paths
  • Disease Spreading
  • Network Flows
  • Parameterized Algorithms
  • NP-hard Problems

Metrics

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

References

  1. Infection prevention and control and preparedness for covid-19 in healthcare settings, 2020. URL: https://www.ecdc.europa.eu/en/publications-data/infection-prevention-and-control-and-preparedness-covid-19-healthcare-settings.
  2. Eleni C. Akrida, George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. 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. URL: https://doi.org/10.1016/j.jcss.2020.05.005.
  3. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Christoforos L. Raptopoulos. The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120:179-193, 2021. URL: https://doi.org/10.1016/j.jcss.2021.04.001.
  4. 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), pages 149:1-149:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.149.
  5. Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, and Rolf 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. Kenneth 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.
  7. Hans L. Bodlaender and Tom C. van der Zanden. On exploring always-connected temporal graphs of small pathwidth. Information Processing Letters, 142:68-71, 2019. URL: https://doi.org/10.1016/j.ipl.2018.10.016.
  8. Dirk Brockmann and Dirk Helbing. The hidden geometry of complex, network-driven contagion phenomena. Science, 342(6164):1337-1342, 2013. URL: https://doi.org/10.1126/science.1245200.
  9. Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Internation Journal of Foundations of Computer Science, 14(02):267-285, 2003. URL: https://doi.org/10.1142/S0129054103001728.
  10. Sebastian Buß, Hendrik Molter, Rolf Niedermeier, and Maciej Rymar. Algorithmic aspects of temporal betweenness. In Proceedings of the 26th SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 2084-2092, 2020. URL: https://doi.org/10.1145/3394486.3403259.
  11. Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC), volume 181, pages 30:1-30:18, 2020. To appear in Algorithmica. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.30.
  12. Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. Journal of Computer and System Sciences, 121:1-17, 2021. URL: https://doi.org/10.1016/j.jcss.2021.04.004.
  13. Vittoria Colizza, Alain Barrat, Marc Barthélemy, and Alessandro Vespignani. The role of the airline transportation network in the prediction and predictability of global epidemics. Proceedings of the National Academy of Sciences of the United States of America, 103(7):2015-2020, 2006. URL: https://doi.org/10.1073/pnas.0510525103.
  14. Daryl J Daley and David G Kendall. Epidemics and rumours. Nature, 204(4963):1118-1118, 1964. URL: https://doi.org/10.1038/2041118a0.
  15. Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying. In Proceedings of the 34th Conference on Artificial Intelligence (AAAI), pages 9810-9817, 2020. URL: https://doi.org/10.1609/aaai.v34i06.6533.
  16. Reinhard Diestel. Graph Theory, volume 173. Springer, 5 edition, 2016. URL: https://doi.org/10.1007/978-3-662-53622-3.
  17. Edsger W Dijkstra et al. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  18. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  19. 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. URL: https://doi.org/10.1098/rspb.2003.2554.
  20. Jessica Enright and Kitty Meeks. Deleting edges to restrict the size of an epidemic: a new application for treewidth. Algorithmica, 80(6):1857-1889, 2018. URL: https://doi.org/10.1007/s00453-017-0311-7.
  21. Jessica Enright, Kitty Meeks, George B. Mertzios, and Viktor 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.
  22. Jessica Enright, Kitty Meeks, and Fiona 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.
  23. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1-18, 2021. URL: https://doi.org/10.1016/j.jcss.2021.01.005.
  24. Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two moves per time step make a difference. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, pages 141:1-141:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.141.
  25. Thomas Erlebach and Jakob T. Spooner. Faster exploration of degree-bounded temporal graphs. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 117, pages 36:1-36:13, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.36.
  26. Thomas Erlebach and Jakob T. Spooner. Non-strict temporal exploration. In Proceedings of the 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 12156, pages 129-145, 2020. URL: https://doi.org/10.1007/978-3-030-54921-3_8.
  27. 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. URL: https://doi.org/10.1126/science.abb6936.
  28. 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. URL: https://doi.org/10.1016/j.tcs.2019.03.031.
  29. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956. URL: https://doi.org/10.4153/CJM-1956-045-5.
  30. L. R. Ford, Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962. URL: https://doi.org/10.1515/9781400875184.
  31. William Goffman and V Newill. Generalization of epidemic theory. Nature, 204(4955):225-228, 1964. URL: https://doi.org/10.1038/204225a0.
  32. 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), volume 12301, pages 200-212, 2020. URL: https://doi.org/10.1007/978-3-030-60440-0_16.
  33. John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378, 1973. URL: https://doi.org/10.1145/362248.362272.
  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. URL: https://doi.org/10.1006/jcss.2002.1829.
  35. George B Mertzios, Othon Michail, and Paul G Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4):1416-1449, 2019. URL: https://doi.org/10.1007/s00453-018-0478-6.
  36. Andrew Mitchell, David Bourn, J Mawdsley, William Wint, Richard Clifton-Hadley, and Marius Gilbert. Characteristics of cattle movements in britain-an analysis of records from the cattle tracing system. Animal Science, 80(3):265-273, 2005. URL: https://doi.org/10.1079/ASC50020265.
  37. Romualdo Pastor-Satorras and Alessandro Vespignani. Epidemic spreading in scale-free networks. Physical Review Letters, 86(14):3200, 2001. URL: https://doi.org/10.1103/PhysRevLett.86.3200.
  38. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):1-24, 2008. URL: https://doi.org/10.1145/1391289.1391291.
  39. Walter J Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. URL: https://doi.org/10.1016/S0022-0000(70)80006-X.
  40. Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun 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.
  41. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf 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 Imprint Privacy Contact