Reducing Reachability in Temporal Networks

The concept of reachability sets (i.e. which vertices in a network can be reached by travelling along edges from a given starting vertex) is central to many network-based processes, including the dissemination of information or the spread of disease through a network. Depending on the application, it might be desirable to increase or decrease the number of vertices that are reachable from any one starting vertex. In most applications, time plays a crucial role: each contact between individuals, represented by an edge, will only occur at certain time(s), when the corresponding edge is "active". The relative timing of edges is clearly crucial in determining the reachability set of any vertex in the network.

In this talk, I will address the problems of reducing the maximum reachability of any vertex in a given temporal network by two different means:

(1) we can remove a limited number of time-edges (times at which a single edge is active) from the network, or

(2) the number of timesteps at which each edge is active is fixed, but we can change the relative order in which different edges are active (perhaps subject to constraints on which edges must be active simultaneously, or restrictions on the timesteps available for each edge).

Mostly, we find that these problems are computationally intractable even when very strong restrictions are placed on the input, but we identify a small number of special cases which admit polynomial-time algorithms, as well as some general upper and lower bounds on what can be achieved.

Everything in this talk is based on joint work with Jessica Enright (University of Edinburgh); I will also mention some joint results with George B. Mertzios and Viktor Zamaraev (University of Durham) and Fiona Skerman (Uppsala University).