Assigning times to minimise reachability in temporal graphs

Temporal graphs (in which edges are active at specified times) are of particular relevance for spreading processes on graphs, e.g. the spread of disease or dissemination of information. Motivated by real-world applications, modification of static graphs to control this spread has proven a rich topic...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2021-02, Vol.115, p.169-186
Main Authors: Enright, Jessica, Meeks, Kitty, Skerman, Fiona
Format: Article
Language:English
Subjects:
Graph contagion
Graph modification
Influence spreading
Parameterized algorithms
Temporal paths
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Temporal graphs (in which edges are active at specified times) are of particular relevance for spreading processes on graphs, e.g. the spread of disease or dissemination of information. Motivated by real-world applications, modification of static graphs to control this spread has proven a rich topic for previous research. Here, we introduce a new type of modification for temporal graphs: the number of active times for each edge is fixed, but we can change the relative order in which (sets of) edges are active. We investigate the problem of determining an ordering of edges that minimises the maximum number of vertices reachable from any single starting vertex; epidemiologically, this corresponds to the worst-case number of vertices infected in a single disease outbreak. We study two versions of this problem, both of which we show to be NP-hard, and identify cases in which the problem can be solved or approximated efficiently.
ISSN:0022-0000
1090-2724
1090-2724
DOI:10.1016/j.jcss.2020.08.001