In this paper an efficient computation schemefor analyzing the security of power transmission networks ispresented. In order to strategically allocate protection devicesin the network, the problem of finding the sparsest stealthy falsedata attack to the state estimator is studied. While the attacksearch problem is traditionally solved as a generic constrainedcardinality minimization problem, this paper exploits the problemstructure intrinsic to the power network application toobtain a polynomial time approximate algorithm based on aminimum cut relaxation. Experiment results from realistic testcases are presented to demonstrate the efficiency and accuracyof the proposed algorithm.