# Temporal Reachability Minimization: Delaying vs. Deleting

arXiv: https://arxiv.org/abs/2102.10814 · HTML: https://mlsanity.com/paper/2102.10814/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2021.

## Built on by (most cited first, 1 of 1)

- [Approximating Optimal Labelings for Temporal Connectivity](https://mlsanity.com/paper/2504.16837/) (2025)

## Abstract (arXiv)

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.