Complexity and Inapproximability Results for the Power Edge Set Problem

Monitoring an electrical network is an important and challenging task. To ensure ongoing reliability and quality of electricity supply to customers, the state of the electrical network must be monitored continuously. The state of such a network is usually defined as the values of all voltages on its nodes and the branch currents. Phasor measurement units (PMUs) are monitoring devices that can be used for this purpose. PMUs are designed to be placed at (sub)stations and can measure their voltage and the current on all their outgoing transmission lines. It is not necessary to place PMUs at all stations, as some of the currents and voltages can be deduced using Ohm and Kirchhoff Laws. Due to their high cost, finding a placement of PMUs that minimizes their number while still ensuring monitoring of the whole network is an important problem. 

Some of the PMUs available in the market have a limited number of channels. A PMU with k channels installed at a vertex can observe only this vertex and k of its neighbors. The identity of these k neighbors is determined at the time of installation. We consider PMUs with a single channel that when placed at vertex observe only this vertex and one of its neighbors. In this case we can equivalently view this as placing the PMUs on edges, where a PMU placed on an edge is assumed to observe both its endpoints.

The Power Edge Set Problem: To minimize cost we need to find a subset of edges of minimum cardinality such that all the vertices in the network are observed by placing PMUs on these edges. The identity of the observed vertices is determined by the following two rules: (R1) if a PMU is placed on an edge then two its endpoints are observed; (R2) if all the neighbors of an observed vertex except one are observed, then this latter vertex is also observed.  

The Power Edge Set Problem is hard to approximate in general graphs within some constant, unless P=NP. This is shown using a reduction from the Min Vertex Cover Problem restricted to 3-regular graphs. This problem is NP-hard to approximate within a factor of 1.36.

The Power Edge Set Problem can be solved in polynomial time on grid and tree networks.