  The power grid and the communication network are highly interdependent on
each other for their well being. In recent times the research community has
shown significant interest in modeling such interdependent networks and
studying the impact of failures on these networks. Although a number of models
have been proposed, many of them are simplistic in nature and fail to capture
the complex interdependencies that exist between the entities of these
networks. To overcome the limitations, recently an Implicative Interdependency
Model that utilizes Boolean Logic, was proposed and a number of problems were
studied. In this paper we study the entity hardening problem, where by entity
hardening we imply the ability of the network operator to ensure that an
adversary (be it Nature or human) cannot take a network entity from operative
to inoperative state. Given that the network operator with a limited budget can
only harden k entities, the goal of the entity hardening problem is to identify
the set of k entities whose hardening will ensure maximum benefit for the
operator, i.e. maximally reduce the ability of the adversary to degrade the
network. We show that the problem is solvable in polynomial time for some
cases, whereas for others it is NP-complete. We provide the optimal solution
using ILP, and propose a heuristic approach to solve the problem. We evaluate
the efficacy of our heuristic using power and communication network data of
Maricopa County, Arizona. The experiments show that our heuristic almost always
produces near optimal results.
