  We study the robustness of interdependent networks where two networks are
said to be interdependent if the operation of one network depends on the
operation of the other one, and vice versa. In this paper, we propose a model
for analyzing bidirectional interdependent networks with known topology. We
define the metric MR(D) to be the minimum number of nodes that should be
removed from one network to cause the failure of D nodes in the other network
due to cascading failures. We prove that evaluating this metric is not only
NP-complete, but also inapproximable. Next, we propose heuristics for
evaluating this metric and compare their performances using simulation results.
Finally, we introduce two closely related definitions for robust design of
interdependent networks; propose algorithms for explicit design, and
demonstrate the relation between robust interdependent networks and expander
graphs.
