Temporal Reachability Minimization: Delaying vs. Deleting
From MaRDI portal
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.
Cited in
(9)- Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes
- Optimizing reachability sets in temporal graphs by delaying
- Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks
- Temporal reachability minimization: delaying vs. deleting
- The complexity of computing optimum labelings for temporal connectivity
- Finding a minimum source set in temporal graphs
- Temporalizing digraphs via linear-size balanced bi-trees
- Temporal graph realization from fastest paths
- Structural parameters for dense temporal graphs
This page was built for publication: Temporal Reachability Minimization: Delaying vs. Deleting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6113364)
