  Inspired by real world examples, e.g. the Internet, researchers have
introduced an abundance of strategic games to study natural phenomena in
networks. Unfortunately, almost all of these games have the conceptual drawback
of being computationally intractable, i.e. computing a best response strategy
or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in
the field is to find tractable realistic network formation models.
  We address this challenge by investigating a very recently introduced model
by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a
strong adversary who attacks (and kills) nodes in the network and lets this
attack spread virus-like to neighboring nodes and their neighbors. Our main
result is to establish that this natural model is one of the few exceptions
which are both realistic and computationally tractable. In particular, we
answer an open question of Goyal et al. by providing an efficient algorithm for
computing a best response strategy, which implies that deciding whether the
game has reached a Nash equilibrium can be done efficiently as well. Our
algorithm essentially solves the problem of computing a minimal connection to a
network which maximizes the reachability while hedging against severe attacks
on the network infrastructure and may thus be of independent interest.
