2026-07-26T21:06:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14516 2024-03-06T10:54:13Z ddc:004 open_access

Temporal Reachability Minimization: Delaying vs. Deleting Molter, Hendrik Renken, Malte Zschoche, Philipp Temporal Graphs Temporal Paths Disease Spreading Network Flows Parameterized Algorithms NP-hard Problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hendrik Molter and Malte Renken and Philipp Zschoche 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.76 urn:nbn:de:0030-drops-145161 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.76 eng https://creativecommons.org/licenses/by/4.0/legalcode