Complexity and inapproximability results for the Power Edge Set problem

Abstract

We consider the single channel PMU placement problem called the Power Edge Set problem. In this variant of the PMU placement problem, (single channel) PMUs are placed on the edges of an electrical network. Such a PMU measures the current along the edge on which it is placed and the voltage at its two endpoints. The objective is to find the minimum placement of PMUs in the network that ensures its full observability, namely measurement of all the voltages and currents. We prove that PES is NP-hard to approximate within a factor (1.12)-$\epsilon$, for any $\epsilon > 0$. On the positive side we prove that PES problem is solvable in polynomial time for trees and grids.

1 Introduction

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 (Manousakis et al. 2012). Note that 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.

Let the electrical network be modelled by a graph where the vertices represent electrical nodes and the edges correspond to transmission lines joining two nodes. The (multi channel) PMU placement problem, also called the power dominating set (PDS) problem, consists of finding a minimum number of PMUs to install on the vertices such that all the graph is observed, that is, all voltages and currents are measured. Brueni and Heath (2005) showed that the observability of a graph by (multi channel) PMUs can be defined by two rules: (R1) if a PMU is placed at a vertex then this vertex and all its neighbours are observed; (R2) if all the neighbours of an observed vertex except one are observed, then this latter is observed.

Several complexity results have been shown for PDS: NP-completeness proofs for bipartite, cographs (Haynes et al. 2002), and planar bipartite graphs (Brueni and Heath 2005), and polynomial-time algorithms for trees, grids (Dorfling and Henning 2006), block graphs (Xu et al. 2006), and bounded treewidth (Guo et al. 2005). Approximation algorithms and hardness results are presented in Aazami and Stilp (2007): $O(\sqrt{n})$-approximation for planar graphs and NP-hardness of approximability within a factor $2^{\log ^{1-\epsilon } n}$. Also, various solution methods have been proposed to solve the PMU placement problem (Manousakis et al. 2012).

Some of the PMUs available in the market have a limited number of channels. A PMU with k channels installed at a vertex v can observe only v and k of its neighbors (and the edges connecting v to these k 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 v observe only v and one of its neighbors. Suppose that the single neighbor of v observed by the PMU is u. Since both v and u are observed, we can equivalently view this as placing the PMU on the edge (v, u), where a PMU placed on an edge is assumed to observe both its endpoints.

The observability of a graph using single channel PMUs can also be determined by two rules similar to the multi channel case. The second rule (R2) is the same as above while (R1) needs to be modified to account for the single channel to: ($R1_E$) if a PMU is installed on an edge then its two endpoint vertices are observed. The objective is to find a minimum placement of single channel PMUs that ensures the observability of the whole graph. We call this problem the Power Edge Set (PES) problem.

Emami et al. proposed a binary linear program for this PMU placement problem (Emami and Abur 2010), which considers only rule $R1_E$, and hence turns out to be equivalent to the minimum edge cover problem, which has polynomial-time solution. The authors discussed the consideration of a restricted version of R2 in Emami et al. (2008). In Poirion et al. (2016), we studied this problem from a practical point of view. We first proposed a naturally iterative index binary linear model that turns out to be too large for practical purposes. Using a fixed point argument, we removed the iteration indices and obtained a bilevel formulation. We then reformulated the latter to a single-level mixed-integer linear program, which performs better than the natural formulation. We then provided a cutting plane algorithm that solves the bilevel program much faster than an off-the-shelf solver can solve the previous models. In this paper, we study the complexity of this problem when both rules of observability are considered. We show that the PES problem is NP-hard to approximate within a factor (1.12)-$\epsilon$, for any $\epsilon >0$. We also prove that it is polynomial-time solvable for trees and grids.

2 Problem statements and preliminaries

Let $G=(V,E)$ be an undirected graph with $|V|=n$. Denote by N(v) the set of neighbors of a vertex $v \in V$. G is k-regular if all vertices have a degree k.

Given a subset $S \subseteq V$, define the set $B(S) \subseteq V$ of “observed” vertices starting at S. Initially, B(S) is set to be S. Then, as long as there exists a vertex $v \notin B(S)$ such that v has a neighbor $u \in B(S)$ and $N(u) \setminus \{v\} \subseteq B(S)$, i.e., v is the only neighbor of u that is not in B(S), then v is added to B(S) (rule R2). In this case, we say that u is the parent of v and v is the child of u. Note that each parent has at most one child and each child has exactly one parent. We extend the parent/child relations to ancestor/descendant relations in a natural way.

In the Power Edge Set (PES) problem, we are given a subset of edges $F\subseteq E$ and the initial set of observed vertices S(F) is the set of all endpoints of the edges in F (rule $R1_E$). B(S(F)) is constructed as describe above (rule R2). We say that F is a Power Edge Set (PES) if $B(S(F))=V$. The Power Edge Set problem is to select a PES F of minimum cardinality.

Power Edge Set Problem

Input: A graph $G=(V,E)$.

Output: A minimum cardinality set $F\subset E$ such that $B(S(F))=V$.

To establish the NP-hardness approximation result, we use the notion of an E-reduction described in the following.

E -reduction Consider an NP Optimization problem and an instance I of this problem. We denote |I| the size of I, opt(I) the optimum value of I, and val(I, S) the value of a feasible solution S of I. The approximation factor r(I, S) of S is given by $\max \left\{ \frac{val(I,S)}{opt(I)}, \frac{opt(I)}{val(I,S)}\right\}$. The error of S, noted $\varepsilon (I,S)$, is defined by $\varepsilon (I,S)= r(I,S)-1.$

For a function f, an algorithm is an f(n)-approximation, if for every instance I of the problem, it returns a solution S such that $r(I,S) \le f(|I|).$

Khanna et al. (1999) introduced the notion of an E-reduction (error-preserving reduction). A problem $\varPi$ is called E -reducible to a problem $\varPi '$, if there exist polynomial time computable functions f, g and a constant $\beta$ such that

• f maps an instance I of $\varPi$ to an instance $I'$ of $\varPi '$ such that opt(I) and $opt(I')$ are related by a polynomial factor, i.e. there exists a polynomial p such that $opt(I')\le p(|I|) opt(I)$,

• g maps any solution $S'$ of $I'$ to one solution S of I such that $\varepsilon (I,S)\le \beta \varepsilon (I',S')$.

An important property of an E-reduction is that it can be applied uniformly to all levels of approximability; that is, if $\varPi$ is E-reducible to $\varPi '$ and $\varPi '$ belongs to $\mathcal {C}$ then $\varPi$ belongs to $\mathcal {C}$ as well, where $\mathcal {C}$ is a class of optimization problems with any kind of approximation guarantee (see also Khanna et al. 1999).

3 NP-hardness of approximation for PES

We prove that PES is hard to approximate within some constant, unless P=NP. To this end, we define an E-reduction from Min Vertex Cover restricted to 3-regular graphs. This problem is NP-hard to approximate within a factor of 1.36 (Dinur and Safra 2005; Feige 2003). We first describe our reduction.

Let I be an instance of Min Vertex Cover formed by a 3-regular graph $G=(V,E)$. We construct an instance $I'$ of PES consisting of a graph $G'=(V',E')$ as follows (see Fig. 1). We associate to each vertex $v \in V$ a gadget $\mathcal {G}_{v}$ in $G'$ (see Fig. 2). For $v \in V$, $\mathcal {G}_{v}$ is composed of 10 vertices $\{v_0,\ldots , v_9\}$. For each edge $(v,u) \in E$, we add the edge $(v_i,u_j)$ to $E'$ for one $i \in \{1,2,3\},$ and $u_j \in \mathcal {G}_{u}$ for one $j \in \{1,2,3\}$. The vertex subsets $\{v_1,\ldots ,v_5\}$ and $\{v_6,\ldots ,v_9\}$ form two cliques linked to each other by the edges $\{v_i,v_{i+5}\},\ i=1,\ldots ,4$. We also add the edge $(v_0, v_5)$ to $E'$. Let u, w, t be the three neighbors of $v \in V$. Without lose of generality, we assume that $(v_1,u_1), (v_2,w_2)$, and $(v_3,t_3)$ are in $E'$, for $v_i \in \mathcal {G}_{v}, i=1,2,3$, $u_1 \in \mathcal {G}_{u}$, $w_2 \in \mathcal {G}_{w}$ and $t_3 \in \mathcal {G}_{t}$. The vertices $u_1,\ w_2$, and $t_3$ are called “neighbor vertices” of $\mathcal {G}_{v}$ and $v_1,v_2,v_3$ its junction vertices.

Fig. 1

Gadget associated to a vertex, $u \in V$ with three neighbors v, w and t

Fig. 2

Gadget $\mathcal {G}_{v}$ associated to a vertex $v \in V$. $u_1,w_2$ and $t_3$ are vertices of $\mathcal {G}_{u}$, $\mathcal {G}_{w}$ and $\mathcal {G}_{t}$ respectively where u, w and t are the adjacent vertices of v in G

In the following, we present four results on the number of PMUs to install according to the degree of vertices and the observability status of the junction and/or neighbor vertices.

Lemma 1

Let $G=(V,E)$ be a connected graph with at least four vertices, such that only one PMU is placed at a given edge $\{u,v\}$ of the graph. If no vertex of G has degree 2, then it is impossible that all the vertices of G are observed.

Proof

By the PMU placed at $\{u,v\}$, the vertices u and v are observed using $R1_E$. Since no vertex in G has degree 2, d(u) or d(v) is at least 3 (either both have degree at least 3 or one has degree 1 and the other degree at least 3). Let us assume that $d(u) \ge 3$. The vertex u has then at least 2 adjacent vertices that are not observed. The same holds if $d(v)\ge 3$. Then R2 cannot be used at either u or v. Then G is not observed. $\square$

Definition 1

Given a gadget $\mathcal {G}_{v}$ in $G'$, a junction vertex $v_i$ of $\mathcal {G}_{v}$, $i \in \{1,2,3\}$, is “observed externally” if $v_i$ can be observed by applying R2 on the neighbor vertex of $\mathcal {G}_{v}$ adjacent to $v_i$.

Lemma 2

Given a gadget $\mathcal {G}_{v}$ of $G'$, the placement of two PMUs is sufficient to observe all the vertices of $\mathcal {G}_{v}$ and its neighbor vertices. Furthermore, unless the neighbor vertices are observed externally, two PMUs are also necessary to observe all the vertices of the gadget.

Proof

We place one PMU on $\{v_6,v_7\}$ and one on $\{v_8,v_9\}$. The vertices $v_6,\ldots ,v_9$ are observed by $R1_E$. Using R2, the vertices $v_{i-5}$, for $i=6,\ldots ,9$, are then observed. By applying R2 to $v_4$ (which is now observed), the vertices $v_5$ and then $v_0$ are observed. Finally applying R2 to the junction vertices allow us to observe the neighbor vertices.

Now assume that all neighbor vertices of $\mathcal {G}_{v}$ are not observed and that only one PMU installed in $\mathcal {G}_{v}$ is sufficient to observe all the vertices of $\mathcal {G}_{v}$. By Lemma 1, $\mathcal {G}_{v}$ cannot be observed by only one PMU since no vertex in $\mathcal {G}_{v}$ has a degree 2, contradiction. Then, at least two PMUs need to be installed. $\square$

Lemma 3

Given a gadget $\mathcal {G}_{v}$ of $G'$ where $v_1, v_2$ and $v_3$ are observed externally, one PMU is necessary and sufficient to observe all the remaining vertices of $\mathcal {G}_{v}$.

Proof

For each $i \in \{1,2,3\},$ $v_i$ has three non-observed adjacent vertices, with $v_4$ and $v_5$ in common. It is then impossible to observe all the vertices of $\mathcal {G}_{v}$ with no PMU. Let us place one PMU on $\{v_4,v_5\}$. Using R2 on $v_5$, $v_0$ is observed. Furthermore, since all the vertices of the clique $\{v_1,\ldots ,v_5\}$ are now observed, for $i\in \{6,\ldots ,9\}$, the vertices $v_i$ are observed by applying R2 on $v_{i-5}$. $\square$

Lemma 4

Given a gadget $\mathcal {G}_{v}$ of $G'$, such that at most two vertices of $\mathcal {G}_{v}$ are observed externally, then the remaining vertices of $\mathcal {G}_{v}$ cannot be observed if only one PMU is placed in $\mathcal {G}_{v}$.

Proof

Assume that $v_1$ and $v_2$ are observed externally (by symmetry we can prove the two other cases) and that only one PMU is installed in $\mathcal {G}_{v}$. The vertices $v_1$ and $v_2$ have each four non-observed adjacent vertices, with vertices $v_3, v_4$ and $v_5$ in common. Placing the PMU on one of the edges linking $v_1$ and $v_2$ to these non-observed vertices will not allow us to apply R2. Similarly, $v_3$ and $v_4$ having three non-observed adjacent vertices, $v_5$ having three non-observed adjacent vertices, and $v_6,\ldots ,v_9$ having at least three non-observed adjacent vertices, R2 cannot be used. Therefore, one PMU is not sufficient to observe $\mathcal {G}_{v}$. $\square$

We now present our inapproximability result.

Theorem 1

PES is NP-hard to approximate within a factor (1.12)-$\epsilon$, for any $\epsilon >0$.

Proof

We prove first that $opt(I')$ and opt(I) are polynomially related. Consider an optimal solution $C^*$ of I. Let $\varPi = \{ \{v_6,v_7\}, \{v_8,v_9\}: v \in C^* \} \cup \{ \{v_4,v_5\}: v \not \in C^* \}$ be the placement consisting of installing two PMUs in the gadgets associated to vertices in $C^*$ and one PMU in the other gadgets. According to Lemma 2, all the vertices of $\mathcal {G}_{v}, v\in C^*$ and their neighbor vertices are observed. For $v \not \in C^*$, its neighbor vertices $u,w,t \in C^*$ are observed since otherwise the edges (v, u), (v, w) and (v, t) are not covered. Then two PMUs are installed in $\mathcal {G}_{u}$, $\mathcal {G}_{w}$ and $\mathcal {G}_{t}$, and by Lemma 2, all their neighbor vertices that include $v_1$, $v_2$ and $v_3$, are observed. Hence, by Lemma 3, the remaining vertices of $\mathcal {G}_{v}$ can be observed by placing only one PMU in $\mathcal {G}_{v}$. Therefore, $opt(I') \le |\varPi |=opt(I)+n$.

Since $|C^*| \ge \frac{2}{27} (n-1)$, we have that $n \le \frac{27}{2} opt(I)+1$. Then $opt(I') \le \frac{31}{2}opt(I)$. Therefore, for n large enough, $opt(I') \le n \; opt(I)$.

Consider now a solution $F \subset E'$ of $I'$. In F, PMUs can be installed on edges between gadgets and some gadgets can have more than two PMUs placed on them. We show that there exists another solution $F'$ of $I'$ that is at least as good as F and containing no PMUs on the edges linking gadgets and only one or two PMUs by gadget.

• 1. If a PMU is placed on $\{u_1,v_1\}$ the edge linking $\mathcal {G}_{u}$ and $\mathcal {G}_{v}$ (the other cases are symmetric). If $v_i$, for $i \in \{2,\ldots ,6\}$, is the child of $v_1$ then $F'= F \setminus \{\{u_1,v_1\}\} \cup \{\{v_1,v_i\}\}$. Since all the vertices of $\mathcal {G}_{v}$ are observed (F is a PES), $u_1$ can be observed using R2 on $v_1$. If $v_1$ has no child then $F'= F \setminus \{\{u_1,v_1\}\}$. Since all the other vertices of $\mathcal {G}_{v}$ are observed (F is a PES), $v_1$ is observed by one of $v_i$, for $i \in \{2,\ldots ,6\}$. $u_1$ can be observed using R2 on $v_1$.

• 2. There are at least 3 PMUs installed in a given gadget $\mathcal {G}_{v}$. Let $F_v$ be subset of edges of $\mathcal {G}_{v}$ where a PMU is installed. The construction of $F'$ depends on the observability of neighbor vertices $u_1$, $w_2$ and $t_3$ of $\mathcal {G}_{v}$. We distinguish 3 cases:

  • a. All the neighbor vertices are observed: by Lemma 3, only one PMU is necessary and sufficient to observe $\mathcal {G}_{v}$. Then considering the placement proposed in Lemma 3, $F'= F \setminus F_v \cup \{\{v_4,v_5\}\}$.

  • b. All the neighbor vertices are not observed: By Lemma 2, only two PMUs are necessary and sufficient to observe $\mathcal {G}_{v}$. Then considering the placement proposed in Lemma 2, $F'= F \setminus F_v \cup \{\{v_6,v_7\},\{v_8,v_9\}\}$.

  • c. At most 2 are observed: By Lemma 4, one PMU is not enough to observe all the vertices of $\mathcal {G}_{v}$. By Lemma 2, two PMUs are sufficient to observe all the vertices of $\mathcal {G}_{v}$. Then considering the placement proposed in Lemma 2, $F'= F \setminus F_v \cup \{\{v_6,v_7\},\{v_8,v_9\}\}$.

Therefore, $F'$ is such that $|F'| \le |F| \le k$, all the PMUs are only placed on edges of gadgets and each gadget has either one or two PMUs installed on it.

Consider $\mathcal {C}=\{u: \mathcal {G}_{u}\; \text {has two PMUs installed on it} \}$ a subset of vertices in G. We prove that $\mathcal {C}$ is a cover by contradiction. We assume that there exists an edge $\{u,v\}$ that is not covered by $\mathcal {C}$, i.e. $u, v \not \in \mathcal {C}$. Thus, $\mathcal {G}_{u}$ and $\mathcal {G}_{v}$ has only one PMU installed on them on $G'$. By Lemmas 3 and 4, $u_1, u_2$, and $u_3$ are externally observed and so are $v_1, v_2$ ,and $v_3$. If we assume that $\{u_1,v_1\}$ is the edge linking $\mathcal {G}_{u}$ and $\mathcal {G}_{v}$, then $u_1$ is observed externally by $v_1$ using R2 and $v_1$ is observed externally by $u_1$ using R2, which is impossible, contradicting the assumption that $F'$ is a PES of $I'$. Then $\mathcal {C}$ is a cover and $val(I,\mathcal {C})=val(I',F')-n$. In particular, when $F'$ is an optimum solution, we have $opt(I')=val(I,\mathcal {C})+n \ge opt(I)+n$. It follows from the previous result that $opt(I')=opt(I)+n$.

Therefore, we have $opt(I') \le n \; opt(I)$ and $\varepsilon (I,\mathcal {C})=\frac{val(I,\mathcal {C})}{opt(I)}-1=\frac{val(I',F')-n}{opt(I')-n}-1= \frac{val(I',F')-opt(I')}{opt(I')-n} =\frac{val(I',F')-opt(I')}{opt(I')} \times \frac{opt(I')}{opt(I')-n}$.

Since I is an instance of a Minimum Vertex Cover defined on a 3-regular graphs we have that $\frac{n}{2} \le opt(I) \le \frac{3n}{4}$ (Feige 2003). Then $\frac{3n}{2} \le opt(I') \le \frac{7n}{4}$. We obtain that $n \le \frac{2opt(I')}{3}$, and we get $\frac{opt(I')}{opt(I')-n} \le 3$. Therefore $\varepsilon (I,\mathcal {C}) \le 3 \frac{val(I',F')-opt(I')}{opt(I')} = 3\; \varepsilon (I',F')$.

Thus, $r(I,\mathcal {C})-1 \le 3(r(I',F')-1)$ and then $r(I',F') \ge \frac{r(I,\mathcal {C})+2}{3}$. Since $r(I,\mathcal {C})=\rho =1.36$, we have $r(I',F') \ge \frac{\rho +2}{3}=1.12$. $\square$

4 Polynomial-time cases for PES

We prove in this section that the PES problem has polynomial-time solutions for trees and grids.

4.1 Trees

We prove that, in trees, PES is equivalent to the Path Cover Problem, defined as follows.

Path Cover Problem

Input: A graph $G=(V,E)$.

Output: A minimum cardinality set of vertex disjoint paths, such that each vertex belongs to a path. (A singleton vertex is also considered a path.)

The Path Cover Problem is NP-hard for general graphs (as the Hamiltonian Path problem is easily reduced to it), but polynomial-time solvable on trees (Moran and Wolfstahl 1991).

Theorem 2

The Power Edge Set problem is polynomial-time solvable on trees. On trees with n vertices, the algorithm runs in O(n) time.

Proof

We prove that PES is equivalent to the Path cover problem.

Consider any solution of the PES problem of size k. We determine the parent-child paths starting from all the endpoints of these k edges. This results in a path cover of size at most 2k. (It will result in less than 2k paths if some edges in the PES share endpoints.) We now show how to reduce the size of the path cover to k. Let $e_1,\ldots ,e_k$ be the edges in the PES. For an edge $e_i$, let $X_i$ and $Y_i$ be the paths starting from the endpoints of $e_i$. We construct the path cover $P_1,\ldots ,P_k$ iteratively. In the i-th iteration, we consider $X_i$ and $Y_i$: if both are not in the current partial cover, we add the path $P_i = (X_i,e_i,Y_i)$ to the partial cover. If only one of $X_i$ or $Y_i$, say $X_i$, is not in the partial cover (implying that $e_i$ shares an endpoint with one of the edges $e_1,\ldots ,e_{i-1}$), add $X_i$ to the partial cover. Note that due to the minimality of the PES, we cannot have a situation where both $X_i$ and $Y_i$ are not in the partial cover. It is easy to see that, after k iterations, we end up with a path cover of size k. Thus, any optimal solution for PES induces a solution of the same cardinality for the Path Cover Problem.

Consider now a path cover $P_1,\ldots ,P_k$. We construct a PES by putting a PMU on the extremity edge of each path. If for some $i=1,\ldots ,k$, $P_i$ is a singleton vertex, we put a PMU on one of its incident edge. We claim that R2 can be applied to observe the rest of the vertices along the paths. We show this by contradiction: suppose that after the vertices in some prefixes of $P_1,\ldots ,P_k$ are observed, we reached a point where R2 cannot be applied anymore. Let $i_1,\ldots ,i_\ell$ be the indices of the $\ell$ paths that still have unobserved vertices, and let $x_{i_j}$ be the last observed vertex in each such path. Consider the vertex $y_{i_1}$ that follows $x_{i_1}$ in path $P_{i_1}$. Since $x_{i_1}$ cannot observe $y_{i_1}$, it must have another unobserved neighbor. This neighbor cannot be on $P_{i_1}$, since then we have a cycle. Assume that this neighbor is on $P_{i_2}$ and consider $x_{i_2}$. Vertex $x_{i_2}$ also has an unobserved neighbor in addition to $y_{i_2}$, but this neighbor cannot be on $P_{i_2}$ and $P_{i_1}$, because in both cases we close a cycle. So assume it is on $P_{i_3}$. We can repeat the process at most k times until we must have a cycle, a contradiction. Then any solution of Path Cover Problem induces a solution of the same cardinality for the PES problem.

Therefore, since the Path cover problem can be solved in O(n) time for trees (Moran and Wolfstahl 1991), we deduce that the PES problem is also solvable in O(n) time for trees. $\square$

4.2 Grids

Let $G_{m \times n}=(V,E)$ be a grid graph that is the graph Cartesian product of $P_m \times P_n$ of path graphs on m and n nodes respectively. We prove in the following that the PES problem is polynomial-time solvable for grids with $opt(G_{m \times n}) = \lceil \frac{1}{2} \min \{m, n\} \rceil$. Let $\ell = \min \{m, n\}$.

Lemma 5

For any optimal solution $S \subseteq E$ of the PES problem and for each $P_i$, for $i=1,\ldots , \ell$, at least one node of $P_i$ is observed by an edge in S using rule $R1_E$.

Proof

Assume that $\ell = m$. For contradiction, assume that Lemma 5 does not hold, i.e., there exists a solution S such that there exists a row path $P_i$, for $i=1,\ldots , m$, with none of its nodes observed using $R1_E$. Consider $P_k$ such a path, $k \in \{1,\ldots , m\}$. Thus its n nodes are observed from n distinct nodes of $P_{k-1}$ or $P_{k+1}$ using rule R2. By the same reasoning, these n nodes of $P_{k-1}$ or $P_{k+1}$ that are not observed by $R1_E$ are observed from the n distinct nodes of $P_{k-2}$ or $P_{k+2}$, and so on until we get to the border of the grid $P_1$ or $P_m$. We deduce that at least n nodes of $G_{m \times n}$ are observed by rule $R1_E$ using at least $\lceil \frac{n}{2}\rceil$ edges in S. However, $G_{m \times n}$ can be observed by exactly $\lceil \frac{m}{2}\rceil$ PMUs. Let $v_1, v_2,\ldots , v_{\lceil m/2 \rceil }$ be the nodes of $P_1$. By placing the PMUs on the edges $\{v_{2i},v_{2i-1}\}$, for $i=1,\ldots ,\lfloor m/2 \rfloor$ and one more PMU on $\{v_{m-1},v_{m}\}$ if m is odd, we can observe the nodes of $P_1$ using $R1_E$ and then all the nodes of $P_k$ from the nodes of $P_{k-1}$ using R2, for $k=2,\ldots ,n$. Hence, S is not optimal, contradiction.

The case $\ell =n$ is proved in a similar way. $\square$

Theorem 3

The Power Edge Set problem is polynomial-time solvable on grids. On grids with size $m \times n$, an optimal solution is obtained in $O(\ell )$ time and its optimal value in O(1) time, with $\ell = \min \{m, n\}$.

Proof

Let S be an optimal solution for the PES problem. By Lemma 5, since at least one node of each $P_i$, for $i=1,\ldots , \ell$, is observed by an edge in S using rule $R1_E$, then $|S| \ge \lceil \frac{\ell }{2}\rceil$. We prove that there exists an optimal solution $S^*$ with size exactly $\lceil \frac{\ell }{2}\rceil$.

Assume that $\ell = m$. As proved in the proof of Lemma 5, if we note $v_1, v_2,\ldots , v_{\lceil m/2 \rceil }$ the nodes of the column path $P_1$, then $S^*$ consists of the set of edges $\{v_{2i},v_{2i-1}\}$, for $i=1,\ldots ,\lfloor m/2 \rfloor$ and the edge $\{v_{m-1},v_{m}\}$ if m is odd. The nodes of $P_1$ are observed using $R1_E$ and then all the nodes of $P_k$ are observed from the nodes of $P_{k-1}$ using R2, for $k=2,\ldots ,n$. We have then $B(\cup ^{m}_{i=1} \{v_i\})=V$.

Now, if $\ell = n$, we consider the row path $P_1$ and denote its nodes by $v_1, v_2,\ldots , v_{\lceil n/2 \rceil }$. As for the previous case we prove that for $S^*$ consisting of the set of edges $\{v_{2i},v_{2i-1}\}$, for $i=1,\ldots ,\lfloor n/2 \rfloor$ and the edge $\{v_{n-1},v_{n}\}$ if n is odd, we have $B(\cup ^{n}_{i=1} \{v_i\})=V$.

Therefore, $S^*$ is an optimal solution for the PES problem and is obtained in $O(\ell )$ time. Its optimal value $opt(G_{m \times n}) = \lceil \frac{1}{2} \min \{m, n\} \rceil$ and is obtained in O(1) time. $\square$

Remark 1

Defining the PES problem using $R1_E$ and R2 gives rise to a natural variant of this problem that corresponds to PMUs with “zero” channels. In this variant PMUs are placed on a vertex and can observe only the vertex they are installed on. The observability of a graph using “zero” channel PMUs can also be determined by two rules. The second rule (R2) is the same as above while (R1) needs to be modified to: ($R1_V$) if a PMU is installed on a vertex then only this vertex is observed. Again, the objective is a minimal placement of PMUs that ensures the observability of the whole graph. We call this problem the Power Vertex Set (PVS) problem. It is also known as the Zero Forcing Set problem (Minimum Rank-Special Graphs Work Group 2008). The PVS problem is NP-hard for general graphs (Aazami 2008) and polynomial-time solvable for trees (Minimum Rank-Special Graphs Work Group 2008).

It is easy to observe that the size of the optimal PVS is lower bounded by the size of the optimal PES, which in turn is lower bounded by the size of the optimal PDS. While the ratio of the optimal PVS size to the optimal PES size is at most 2, the ratio of the optimal PES size to the optimal PDS size may be as large as $n-2$. To see this consider a “star” graph with n vertices and $n-1$ edges. It is easy to see that the PDS size of this graph is 1 (placing the PMU in the center), while the size of the PVS and the PES is $n-2$.

Therefore, we can deduce the following bounds for the optimum value of an instance of the PES problem:

$$\begin{aligned} \max \left\{ \frac{opt(I_{V})}{2},opt(I_{D})\right\} \le opt(I_{E}) \le \min \left\{ opt(I_{V}), (n-2) opt(I_{D})\right\} , \end{aligned}$$

where $I_{V}, I_{E}$ and $I_{D}$ are instances of the PVS, PES and PDS problems.

5 Conclusions

We presented NP-hardness of approximability for the PES problem in general graphs and polynomality results in trees and grids. An interesting avenue for future work would be to study the complexity of this problem on other classes of graphs, such as graphs with bounded treewidth, cographs, and regular and bipartite graphs. We conjecture that PVS and PES are easier than the PDS problem. This can be substantiated by finding a polynomial time algorithm for a class of graphs on which PDS is NP-hard. Another direction for further study is finding approximation algorithms for PES. Also, further work would be to find interesting upper and lower bounds for the optimum value of an instance of the PES problem.