  Given a directed graph (representing a social network), the influence
maximization problem is to find k nodes which, when influenced (or activated),
would maximize the number of remaining nodes that get activated. In this paper,
we consider a more general version of the problem that includes an additional
set of nodes, termed as physical nodes, such that a node in the social network
is covered by one or more physical nodes. A physical node exists in one of two
states at any time, opened or closed, and there is a constraint on the maximum
number of physical nodes that can be opened. In this setting, an inactive node
in the social network becomes active if it has enough active neighbors in the
social network and if it is covered by at least one of the opened physical
nodes. This problem arises in disaster recovery, where a displaced social group
decides to return after a disaster only after enough groups in its social
network return and some infrastructure components in its neighborhood are
repaired. The general problem is NP-hard to approximate within any constant
factor and thus we characterize optimal and approximation algorithms for
special instances of the problem.
