  In this paper, we study the robustness of interdependent networks, in which
the state of one network depends on the state of the other network and vice
versa. In particular, we focus on the interdependency between the power grid
and communication networks, where the grid depends on communications for its
control, and the communication network depends on the grid for power. A
real-world example is the Italian blackout of 2003, when a small failure in the
power grid cascaded between the two networks and led to a massive blackout. In
this paper, we study the minimum number of node failures needed to cause total
blackout (i.e., all nodes in both networks to fail). In the case of
unidirectional interdependency between the networks we show that the problem is
NP-hard, and develop heuristics to find a near-optimal solution. On the other
hand, we show that in the case of bidirectional interdependency this problem
can be solved in polynomial time. We believe that this new interdependency
model gives rise to important, yet unexplored, robust network design problems
for interdependent networked infrastructures.
