This paper presents several advances for the PMU placement problem (PPP). Existing approaches have difficulty scaling to full-scale systems, and are not guaranteed to be resilient to multiple component failures. This paper expands PPP to a more general k-resilient PPP, where any k PMUs and/or lines can fail without jeopardizing the problem's full supervision criterion. Our PPP model — a novel formulation based on maximum-flow network design — is unique in that it is amenable to efficient decomposition, which significantly improves tractability and scalability. We present two cutting plane algorithms to support this decomposition — the first such algorithms for the PPP to our knowledge. The improvements in computational efficiency afforded by the network decomposition suggest that our approach can solve the PPP for large-scale systems.