  Infrastructure systems, such as power systems, often experience cascading
failures. Modeling an infrastructure system as a collection of interdependent
networks has recently received attention as a way to explain cascading
failures. In this study, we propose an approach to find the set of critical
nodes in an interdependent network. For an integer k, we say that a set of k
nodes is critical if the initial failures of these k nodes result in the most
severe cascading failure among all sets of k nodes. This approach adopts the
seminal model of interdependent networks proposed by Buldyrev et al., in which
new link failures occur in a network if the connectivity is lost in the paired
network. The problem of finding critical nodes is NP-hard; thus the aim of the
approach is to accurately solve the problem in feasible time for moderate-size
problem instances. The proposed approach consists of two phases. In the first
phase, the maximum number of failure propagation stages is computed by
repeatedly solving the Boolean satisfiability problem. This number is then used
in the second phase, where the set of critical nodes is computed using integer
linear programming. The results of applying this approach to a variety of
problem instances demonstrate that the approach is feasible for up to at least
30 nodes and can be used as the baseline to compare the performance of
heuristic solutions.
