Electric power network security analysis via minimum cut relaxation

In this paper an efficient computation scheme for analyzing the security of power transmission networks is presented. In order to strategically allocate protection devices in the network, the problem of finding the sparsest stealthy false data attack to the state estimator is studied. While the attack search problem is traditionally solved as a generic constrained cardinality minimization problem, this paper exploits the problem structure intrinsic to the power network application to obtain a polynomial time approximate algorithm based on a minimum cut relaxation. Experiment results from realistic test cases are presented to demonstrate the efficiency and accuracy of the proposed algorithm.