Skip to main content

Research Repository

Advanced Search

Deleting edges to restrict the size of an epidemic in temporal networks

Enright, J.; Meeks, K.; Mertzios, G.B.; Zamaraev, V.

Deleting edges to restrict the size of an epidemic in temporal networks Thumbnail


Authors

J. Enright

K. Meeks

V. Zamaraev



Contributors

Peter Rossmanith
Editor

Pinar Heggernes
Editor

Joost-Pieter Katoen
Editor

Abstract

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of goods over logistical infrastructure. Often, the networks over which these processes spread are dynamic in nature, and can be modeled with graphs whose structure is subject to discrete changes over time, i.e. with temporal graphs. Here, we consider temporal graphs in which edges are available at specified timesteps, and study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path (i.e. a path, along which the times of the edge availabilities increase). We introduce a natural deletion problem for temporal graphs and we provide positive and negative results on its computational complexity, both in the traditional and the parameterised sense (subject to various natural parameters), as well as addressing the approximability of this problem.

Citation

Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019). Deleting edges to restrict the size of an epidemic in temporal networks. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (57:1-57:15). https://doi.org/10.4230/lipics.mfcs.2019.57

Conference Name 44th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Conference Location Aachen, Germany
Acceptance Date Jun 11, 2019
Online Publication Date Aug 23, 2019
Publication Date Aug 31, 2019
Deposit Date Jul 23, 2019
Publicly Available Date Nov 8, 2019
Pages 57:1-57:15
Series Title LIPIcs (Leibniz International Proceedings in Informatics)
Series Number 138
Series ISSN 1868-8969
Book Title 44th International Symposium on Mathematical Foundations of Computer Science
DOI https://doi.org/10.4230/lipics.mfcs.2019.57
Public URL https://durham-repository.worktribe.com/output/1142358

Files






You might also like



Downloadable Citations