Open AccessFundamental limitations on efficiently forecasting certain epidemic measures in network models
Author(s) -
Daniel J. Rosenkrantz,
Anil Vullikanti,
S. S. Ravi,
Richard E. Stearns,
Simon A. Levin,
H. Vincent Poor,
Madhav Marathe
Publication year - 2022
Publication title -
proceedings of the national academy of sciences of the united states of america
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 5.011
H-Index - 771
eISSN - 1091-6490
pISSN - 0027-8424
DOI - 10.1073/pnas.2109228119
Subject(s) - heuristics , computer science , exploit , range (aeronautics) , computational complexity theory , mathematical optimization , algorithm , mathematics , materials science , composite material , operating system , computer security
Significance We show that under widely believed complexity theoretic hypotheses, one cannot expect to find provably correct and efficient algorithms for predicting epidemic dynamics on general networks. These results hold even under idealized problem formulations, where all the model parameters are known and are insensitive to changes in environment. Further, they hold even for a small time horizon with just one random parameter, namely, the transmission probability. Thus, computational complexity poses an inherent challenge to effective and efficient epidemic forecasting in network models. Our results do not rule out heuristics that work well in practice or algorithms that provide provable guarantees for restricted networks. Rather, they suggest that algorithms working across a range of inputs should exploit properties of problem instances.