# Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs

Pierre Cazals, Benoit Darties, Annie Chateau, Rodolphe Giroudeau, Mathias Weller

► To cite this version:

Pierre Cazals, Benoit Darties, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs. IWOCA 2019 - 30th International Workshop on Combinatorial Algorithms, Jul 2019, Pisa, Italy. pp.122-135, 10.1007/978-3-030-25005-8_11 . hal-02359076

HAL Id: hal-02359076

https://hal.science/hal-02359076

Submitted on 9 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs

Pierre Cazals, Benoit Darties, Annie Chateau, Rodolphe Giroudeau, Mathias Weller

► To cite this version:

Pierre Cazals, Benoit Darties, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs. IWOCA 2019 - 30th International Workshop on Combinatorial Algorithms, Jul 2019, Pisa, Italy. pp.122-135, 10.1007/978-3-030-25005-8_11 . hal-02359076

HAL Id: hal-02359076

https://hal.science/hal-02359076v1

Submitted on 9 Jun 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Power Edge Set and Zero Forcing Set remain
difficult in cubic graphs

P. Cazals¹ and B. Darties² and A. Chateau¹,⁴ and R. Giroudeau¹ and M. Weller³

¹ LIRMM - CNRS UMR 5506 - Univ. de Montpellier, France

² Le2i FRE2005, CNRS, Arts et Métiers, Univ. Bourgogne Franche-Comté

³ CNRS - LIGM - Univ. Marne-La-Vallée, France

⁴ IBC - Montpellier, France
{chateau,giroudeau}@lirmm.fr, benoit.darties@u-bourgogne.fr,
mathias.weller@u-pem.fr

**Abstract.** This paper presents new complexity and non-approximation results concerning two color propagation problems, namely POWER EDGE SET and ZERO FORCING SET. We focus on cubic graphs, exploiting their structural properties to improve and refine previous results. We also give hardness results for parameterized precolored versions of these problems. Finally, we give a polynomial-time algorithm for ZERO FORCING SET in proper interval graphs.

**keywords :** Synchrophasor, Power Edge Set, Zero Forcing Set, Complexity

# 1 Introduction

*Motivation.* In power networks, synchrophasors are time-synchronized numbers that represent both the magnitude and phase angle of the sine waves on network links. A Phasor Measurement Unit (PMU) is an expensive measuring device used to continuously collect the voltage and phase angle of a single station and the electrical lines connected to it. The problem of minimizing the number of PMUs to place on a network for complete network monitoring is an important challenge for operators and has gained a considerable attention over the past decade [3, 7, 7, 11, 12, 14, 16, 18, 21, 23, 26]. The problem is known as POWER DOMINATING SET [26] and we state it below. We model the network as a graph $G = (V, E)$ with $|V|=$: *n* and $|E|=$: *m*. We denote the set of vertices and edges of $G$ by $V(G)$ and $E(G)$, respectively. We let $N_G(v)$ denote the set of neighbors of $v \in V$ in $G$ and $d_G(v) = |N_G(v)|$ its degree in $G$. Further, we let $N_G[v] = N_G(v) \cup \{v\}$ denote the closed neighborhood of $v$ in $G$, and we let $G[W]$ denote the subgraph of $G$ induced by vertices $W \subseteq V(G)$. The problem is described through monitoring of nodes of the network, corresponding to monitoring vertices $V(G)$ by PMUs, propagated using the following rules.

**RULE R**₁\*: A vertex *v* of *G* on which a PMU is placed will be called a *monitored* vertex, and all its neighbors vertices $N_G(v)$ automatically become monitored.
Power Edge Set and Zero Forcing Set remain
difficult in cubic graphs

P. Cazals¹ and B. Darties² and A. Chateau¹,⁴ and R. Giroudeau¹ and M. Weller³

¹ LIRMM - CNRS UMR 5506 - Univ. de Montpellier, France

² Le2i FRE2005, CNRS, Arts et Métiers, Univ. Bourgogne Franche-Comté

³ CNRS - LIGM - Univ. Marne-La-Vallée, France

⁴ IBC - Montpellier, France
{chateau,giroudeau}@lirmm.fr, benoit.darties@u-bourgogne.fr,
mathias.weller@u-pem.fr

**Abstract.** This paper presents new complexity and non-approximation results concerning two color propagation problems, namely POWER EDGE SET and ZERO FORCING SET. We focus on cubic graphs, exploiting their structural properties to improve and refine previous results. We also give hardness results for parameterized precolored versions of these problems. Finally, we give a polynomial-time algorithm for ZERO FORCING SET in proper interval graphs.

**keywords :** Synchrophasor, Power Edge Set, Zero Forcing Set, Complexity

# 1 Introduction

*Motivation.* In power networks, synchrophasors are time-synchronized numbers that represent both the magnitude and phase angle of the sine waves on network links. A Phasor Measurement Unit (PMU) is an expensive measuring device used to continuously collect the voltage and phase angle of a single station and the electrical lines connected to it. The problem of minimizing the number of PMUs to place on a network for complete network monitoring is an important challenge for operators and has gained a considerable attention over the past decade [3, 7, 7, 11, 12, 14, 16, 18, 21, 23, 26]. The problem is known as POWER DOMINATING SET [26] and we state it below. We model the network as a graph $G = (V, E)$ with $|V|=$: *n* and $|E|=$: *m*. We denote the set of vertices and edges of $G$ by $V(G)$ and $E(G)$, respectively. We let $N_G(v)$ denote the set of neighbors of $v \in V$ in $G$ and $d_G(v) = |N_G(v)|$ its degree in $G$. Further, we let $N_G[v] = N_G(v) \cup \{v\}$ denote the closed neighborhood of $v$ in $G$, and we let $G[W]$ denote the subgraph of $G$ induced by vertices $W \subseteq V(G)$. The problem is described through monitoring of nodes of the network, corresponding to monitoring vertices $V(G)$ by PMUs, propagated using the following rules.

**RULE R**₁\*: A vertex *v* of *G* on which a PMU is placed will be called a *monitored* vertex, and all its neighbors vertices $N_G(v)$ automatically become monitored.
**RULE R₂**: if all but one neighbor of a monitored vertex are monitored, then this unmonitored vertex will become monitored as well.

Letting $\Gamma_P(G)$ denote the minimum number of PMUs to place on vertices to obtain a full monitoring of the network (using RULE $R_2$), the decision version of the problem is described as follows:

**POWER DOMINATING SET (PDS)**

**Input:** a graph $G = (V, E)$ and some $k \in \mathbb{N}$

**Question:** Is $\Gamma_P(G) \le k$?

**POWER DOMINATING SET** is $\mathcal{NP}$-complete in general graphs [14]. A large amount of literature is devoted to this problem, describing a wide range of approaches, either exact such as integer linear programming [11] or branch-and-cut [21], or heuristic, such as greedy algorithms [16], approximations [4] or genetic algorithms [18]. The problem has also been shown to be polynomial-time solvable on grids [7], but $\mathcal{NP}$-complete in unit-disk graphs [23].

In this paper, we consider two variants of the problem, called **POWER EDGE SET (PES)** [25,24] and **ZERO FORCING SET (ZFS)** [3], which respectively consist in placing PMUs on the *links*, and reducing the monitoring range of a PMU placed on a node. This leads us to replace RULE $R_1^*$ in each of these problems as follows (RULE $R_2$ remains unchanged):

**RULE R₁ (PES):** two endpoints of an edge bearing a PMU are monitored.

**RULE R₁ (ZFS):** only the node bearing a PMU is monitored.

We let $pes(G)$ and $zfs(G)$ denote the minimum number of PMUs to place on the edges, resp. nodes, of $G$ to entirely monitor $G$. Both PES and ZFS can be seen as a problem of color propagation with colors 0 (white) and 1 (black), respectively designating the states *not monitored* and *monitored* of a vertex of $G$. As input to PES or ZFS, we will consider a connected graph $G = (V, E)$. For each vertex $v \in V$, let $c(v)$ be the color assigned to $v$ (we abbreviate $\cup_{v \in X} c(v) =: c(X)$). Before placing the PMUs, we have $c(V) = \{0\}$ and the aim is to obtain $c(V) = \{1\}$ using RULE $R_1$ and RULE $R_2$ while minimizing the number of PMUs. See Figure 1 and Figure 2 for detailed examples illustrating the differences between PES and ZFS.

**POWER EDGE SET (PES)**

**Input:** a graph $G$, some $k \in \mathbb{N}$

**Question:** Is $pes(G) \le k$?

**ZERO FORCING SET (ZFS)**

**Input:** a graph $G$, some $k \in \mathbb{N}$

**Question:** Is $zfs(G) \le k$?

*Related work & our results.* Assigning a minimum number of PMUs to monitor the whole network is known to be $\mathcal{NP}$-hard in general for both PES and ZFS. For the former, preliminary complexity result and a lower bound on approximation of $1.12 - \epsilon$ with $\epsilon > 0$ have been shown by Toubaline et al. [24]. They also present a linear-time algorithm on trees by reduction to PATH COVER. Poirion et al. [20] propose a linear program with binary variables indexed by the necessary iterations using propagation RULE $R_1$ and RULE $R_2$. Recently, inapproximability results have been proposed on special graph classes such as planar or bipartite graphs [5].

In this work, we develop hardness results on complexity and approximation for special cases of POWER EDGE SET and ZERO FORCING SET.
**RULE R₂**: if all but one neighbor of a monitored vertex are monitored, then this unmonitored vertex will become monitored as well.

Letting $\Gamma_P(G)$ denote the minimum number of PMUs to place on vertices to obtain a full monitoring of the network (using RULE $R_2$), the decision version of the problem is described as follows:

**POWER DOMINATING SET (PDS)**

**Input:** a graph $G = (V, E)$ and some $k \in \mathbb{N}$

**Question:** Is $\Gamma_P(G) \le k$?

**POWER DOMINATING SET** is $\mathcal{NP}$-complete in general graphs [14]. A large amount of literature is devoted to this problem, describing a wide range of approaches, either exact such as integer linear programming [11] or branch-and-cut [21], or heuristic, such as greedy algorithms [16], approximations [4] or genetic algorithms [18]. The problem has also been shown to be polynomial-time solvable on grids [7], but $\mathcal{NP}$-complete in unit-disk graphs [23].

In this paper, we consider two variants of the problem, called **POWER EDGE SET (PES)** [25,24] and **ZERO FORCING SET (ZFS)** [3], which respectively consist in placing PMUs on the *links*, and reducing the monitoring range of a PMU placed on a node. This leads us to replace RULE $R_1^*$ in each of these problems as follows (RULE $R_2$ remains unchanged):

**RULE R₁ (PES):** two endpoints of an edge bearing a PMU are monitored.

**RULE R₁ (ZFS):** only the node bearing a PMU is monitored.

We let $pes(G)$ and $zfs(G)$ denote the minimum number of PMUs to place on the edges, resp. nodes, of $G$ to entirely monitor $G$. Both PES and ZFS can be seen as a problem of color propagation with colors 0 (white) and 1 (black), respectively designating the states *not monitored* and *monitored* of a vertex of $G$. As input to PES or ZFS, we will consider a connected graph $G = (V, E)$. For each vertex $v \in V$, let $c(v)$ be the color assigned to $v$ (we abbreviate $\cup_{v \in X} c(v) =: c(X)$). Before placing the PMUs, we have $c(V) = \{0\}$ and the aim is to obtain $c(V) = \{1\}$ using RULE $R_1$ and RULE $R_2$ while minimizing the number of PMUs. See Figure 1 and Figure 2 for detailed examples illustrating the differences between PES and ZFS.

**POWER EDGE SET (PES)**

**Input:** a graph $G$, some $k \in \mathbb{N}$

**Question:** Is $pes(G) \le k$?

**ZERO FORCING SET (ZFS)**

**Input:** a graph $G$, some $k \in \mathbb{N}$

**Question:** Is $zfs(G) \le k$?

*Related work & our results.* Assigning a minimum number of PMUs to monitor the whole network is known to be $\mathcal{NP}$-hard in general for both PES and ZFS. For the former, preliminary complexity result and a lower bound on approximation of $1.12 - \epsilon$ with $\epsilon > 0$ have been shown by Toubaline et al. [24]. They also present a linear-time algorithm on trees by reduction to PATH COVER. Poirion et al. [20] propose a linear program with binary variables indexed by the necessary iterations using propagation RULE $R_1$ and RULE $R_2$. Recently, inapproximability results have been proposed on special graph classes such as planar or bipartite graphs [5].

In this work, we develop hardness results on complexity and approximation for special cases of POWER EDGE SET and ZERO FORCING SET.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** PMU propagation on PES problem: before any PMU placement, all vertices are white (Figure 1a). A PMU on {$b, c$} induces $c(b) = c(c) = 1$ (black) by RULE $R_1$ (Figure 1b). By applying RULE $R_2$ on $b$, we obtain $c(a) = 1$ (Figure 1c). Then RULE $R_2$ on $a$ induces $c(d) = 1$ (Figure 1d), and RULE $R_2$ on $c$ or $d$ induces $c(e) = 1$ (Figure 1e). A second PMU is required to obtain a complete coloring. Placing a PMU on {$e, f$} gives us $c(f) = 1$ by RULE $R_1$ (Figure 1f). Finally, RULE $R_2$ on $e$ induces $c(g) = 1$ (Figure 1g). The set of edges where PMUs have been placed is $S = \{bc, ef\}$, giving ($b, c, a, d, e, f, g$) as a valid order for $G$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** PMU propagation on ZFS problem: before any PMU placement, all vertices are white (Figure 2a). Placing one PMU on {$b$} allows to monitor it. (Figure 2b). Placing a second PMU on {$c$} allows to monitor it (Figure 2c), and now we can apply RULE $R_2$ on $b$, to obtain $c(a) = 1$ (Figure 2d). Then RULE $R_2$ on $a$ induces $c(d) = 1$ (Figure 2e), and RULE $R_2$ on $c$ or $d$ induces $c(e) = 1$ (Figure 2f). A third PMU is required to obtain a complete coloring. For example, placing a PMU on $f$ (Figure 2g) allows to apply RULE $R_2$ on $e$ to obtain $c(g) = 1$ (Figure 2h).</figcaption></figure>
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** PMU propagation on PES problem: before any PMU placement, all vertices are white (Figure 1a). A PMU on {$b, c$} induces $c(b) = c(c) = 1$ (black) by RULE $R_1$ (Figure 1b). By applying RULE $R_2$ on $b$, we obtain $c(a) = 1$ (Figure 1c). Then RULE $R_2$ on $a$ induces $c(d) = 1$ (Figure 1d), and RULE $R_2$ on $c$ or $d$ induces $c(e) = 1$ (Figure 1e). A second PMU is required to obtain a complete coloring. Placing a PMU on {$e, f$} gives us $c(f) = 1$ by RULE $R_1$ (Figure 1f). Finally, RULE $R_2$ on $e$ induces $c(g) = 1$ (Figure 1g). The set of edges where PMUs have been placed is $S = \{bc, ef\}$, giving ($b, c, a, d, e, f, g$) as a valid order for $G$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** PMU propagation on ZFS problem: before any PMU placement, all vertices are white (Figure 2a). Placing one PMU on {$b$} allows to monitor it. (Figure 2b). Placing a second PMU on {$c$} allows to monitor it (Figure 2c), and now we can apply RULE $R_2$ on $b$, to obtain $c(a) = 1$ (Figure 2d). Then RULE $R_2$ on $a$ induces $c(d) = 1$ (Figure 2e), and RULE $R_2$ on $c$ or $d$ induces $c(e) = 1$ (Figure 2f). A third PMU is required to obtain a complete coloring. For example, placing a PMU on $f$ (Figure 2g) allows to apply RULE $R_2$ on $e$ to obtain $c(g) = 1$ (Figure 2h).</figcaption></figure>
Preliminaries. In the following, we will consider a total order $\sigma$ of vertices of a graph $G$ as a sequence $(v_1, v_2, \ldots)$ such that $v_i$ occurs before $v_j$ in the sequence if and only if $v_i <_{\sigma} v_j$.

**Definition 1 (valid order).** Let $G = (V, E)$ be a graph, let $S \subseteq E$ (resp. $S \subseteq V$), and let $\sigma$ be a total order of $V$, such that for each $v \in V(G)$, there is an edge incident to $v$ in $S$ (resp. $v \in S$) or there is a vertex $u \in N_G(v)$ which verifies $N_G[u] \le_{\sigma} v$. Then, $<_{\sigma}$ is called valid for $S$.

Given a graph $G = (V, E)$, any set $S \subseteq V$ (or $S \subseteq E$) such that repeated application of RULE $R_1$ (ZFS) (or RULE $R_1$ (PES)) and RULE $R_2$ leads to $G$ being completely monitored is called a zero forcing set (or power edge set). Using Definition 1, we can formally define the propagation process in $G$. For instance, in Figure 1, a valid order for $S = \{bc, ef\}$ is $(b, c, a, d, e, f, g)$.

**Observation 1** Let $G = (V, E)$ be a graph and let $S \subseteq E$ (resp. $S \subseteq V$). Then, $S$ is a power edge set (res. a zero forcing set) if and only if there is a valid order $\sigma$ on $G$, with respect to $S$.

Note that, for a graph $G = (V, E)$, any set $S \subseteq E$ is a power edge set if and only if $\bigcup_{e \in S} e$ is a zero forcing set for $G$. It is therefore natural and unambiguous to also call such an edge set zero forcing set.

Finally, we call a vertex $v$ propagating to $x \in N_G(v)$ if $c(x) = 0$ and for all $y \in N_G[v] \setminus \{x\}$, we have $c(y) = 1$. Note that each maximal clique of $G$ can contain at most one propagating vertex.

**Lemma 1.** Let $G = (V, E)$ be a graph, let $S$ be a zero forcing set of $G$, and let $C := \{C_1, \ldots, C_c\}$ be a set of maximal cliques in $G$ covering $E$. Then $|V \setminus S| \le c$.

*Proof.* Let $\sigma$ be a valid order for $S$. We show that each $C_i$ contains at most one edge $uv$ such that $v \notin S$ and $N_G[u] \le_{\sigma} v$. Since $C$ covers $E$, this implies $|V \setminus S| \le |C| = c$. Let $C \in \mathcal{C}$ and let $C$ contain an edge $uv$ such that $N_G[u] \le_{\sigma} v$ and $v \notin S$. Then, $C \subseteq N_G[u]$, implying $C \le_{\sigma} v$. Thus, $v$ is the last vertex of $C$ with respect to $\sigma$ and this vertex is unique. $\square$

## 2 Classical Hardness

Most results presented in this section rely on reductions from graph problems using gadgets for vertices or edges of the original instance. We model the propagation process using the notion of valid order with respect to the solution set, whatever the nature of it: set of edges for PES, of vertices for ZFS.

We present new lower bounds for POWER EDGE SET that hold even in the very restricted case that $G$ is cubic (i.e. all vertices in $G$ have degree three). Previous results show that the problem is $\mathcal{NP}$-complete even if $G$ is a subgraph of the grid with bounded degree at most three [5]. In this paper, we show the problem remains $\mathcal{NP}$-complete if $G$ is cubic and planar. The proof is done by
Preliminaries. In the following, we will consider a total order $\sigma$ of vertices of a graph $G$ as a sequence $(v_1, v_2, \ldots)$ such that $v_i$ occurs before $v_j$ in the sequence if and only if $v_i <_{\sigma} v_j$.

**Definition 1 (valid order).** Let $G = (V, E)$ be a graph, let $S \subseteq E$ (resp. $S \subseteq V$), and let $\sigma$ be a total order of $V$, such that for each $v \in V(G)$, there is an edge incident to $v$ in $S$ (resp. $v \in S$) or there is a vertex $u \in N_G(v)$ which verifies $N_G[u] \le_{\sigma} v$. Then, $<_{\sigma}$ is called valid for $S$.

Given a graph $G = (V, E)$, any set $S \subseteq V$ (or $S \subseteq E$) such that repeated application of RULE $R_1$ (ZFS) (or RULE $R_1$ (PES)) and RULE $R_2$ leads to $G$ being completely monitored is called a zero forcing set (or power edge set). Using Definition 1, we can formally define the propagation process in $G$. For instance, in Figure 1, a valid order for $S = \{bc, ef\}$ is $(b, c, a, d, e, f, g)$.

**Observation 1** Let $G = (V, E)$ be a graph and let $S \subseteq E$ (resp. $S \subseteq V$). Then, $S$ is a power edge set (res. a zero forcing set) if and only if there is a valid order $\sigma$ on $G$, with respect to $S$.

Note that, for a graph $G = (V, E)$, any set $S \subseteq E$ is a power edge set if and only if $\bigcup_{e \in S} e$ is a zero forcing set for $G$. It is therefore natural and unambiguous to also call such an edge set zero forcing set.

Finally, we call a vertex $v$ propagating to $x \in N_G(v)$ if $c(x) = 0$ and for all $y \in N_G[v] \setminus \{x\}$, we have $c(y) = 1$. Note that each maximal clique of $G$ can contain at most one propagating vertex.

**Lemma 1.** Let $G = (V, E)$ be a graph, let $S$ be a zero forcing set of $G$, and let $C := \{C_1, \ldots, C_c\}$ be a set of maximal cliques in $G$ covering $E$. Then $|V \setminus S| \le c$.

*Proof.* Let $\sigma$ be a valid order for $S$. We show that each $C_i$ contains at most one edge $uv$ such that $v \notin S$ and $N_G[u] \le_{\sigma} v$. Since $C$ covers $E$, this implies $|V \setminus S| \le |C| = c$. Let $C \in \mathcal{C}$ and let $C$ contain an edge $uv$ such that $N_G[u] \le_{\sigma} v$ and $v \notin S$. Then, $C \subseteq N_G[u]$, implying $C \le_{\sigma} v$. Thus, $v$ is the last vertex of $C$ with respect to $\sigma$ and this vertex is unique. $\square$

## 2 Classical Hardness

Most results presented in this section rely on reductions from graph problems using gadgets for vertices or edges of the original instance. We model the propagation process using the notion of valid order with respect to the solution set, whatever the nature of it: set of edges for PES, of vertices for ZFS.

We present new lower bounds for POWER EDGE SET that hold even in the very restricted case that $G$ is cubic (i.e. all vertices in $G$ have degree three). Previous results show that the problem is $\mathcal{NP}$-complete even if $G$ is a subgraph of the grid with bounded degree at most three [5]. In this paper, we show the problem remains $\mathcal{NP}$-complete if $G$ is cubic and planar. The proof is done by
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** The gadget $H_v$ for a vertex $v$.</figcaption></figure>

reduction from VERTEX COVER (see below) on 3-regular, planar graphs, which is $\mathcal{NP}$-complete [10] but admits a PTAS [1], and a 3/2-approximation [2].

**VERTEX COVER (VC)**

**Input:** a graph $G = (V, E)$, some $k \in \mathbb{N}$.

**Question:** Is there a size-$k$ set $S \subseteq V$ covering $E$, i.e. $\forall e \in E, e \cap S \neq \emptyset$?

**Construction 1** For a given cubic planar graph $G = (V, E)$ with $n$ vertices, we construct a graph $G'$ as follows:

- For each $v \in V$, construct $H_v$ (see Figure 3).

- For each $v \in V$ with $N_G(v) = \{x, y, z\}$, connect $H_x$ to $H_v$ with the edge $v_1x_1$, $H_y$ to $H_v$ with $v_2y_2$ and $H_z$ to $H_v$ with $v_0z_0$.

The graph $G'$ is clearly cubic and planar and Construction 4 is applied in polynomial time. The construction is linear in $n$ and $k$.

**Lemma 2.** The gadget $H_v$ needs at least one PMU to be fully colored: if $x_1, y_2$ and $z_0$ are propagating respectively to $v_1, v_2$ and $v_0$, then one PMU is sufficient; otherwise two PMUs are needed to fully color $H_v$.

*Proof.* First, if $x_1, y_2$ and $z_0$ are propagating respectively to $v_1, v_2$ and $v_0$, then, after application of RULE $R_2$, $c(v_0) = c(v_1) = c(v_2) = 1$. Thus this is the beginning of a valid order: $(v_0, v_1, v_2, v_3, v_5, v_4, v_6, v_7, v_{12}, v_9, v_{10})$. There is no more possible propagation, it is necessary to assign a new PMU. If we place it on the edge $v_{14}v_{16}$, the remainder of a valid order for $H_v$ is: $(v_{14}, v_{16}, v_{11}, v_8, v_{13}, v_{15}, v_{16})$.

Second, we show that $H_v$ may be colored by two PMUs in every case. If PMUs are assigned to the edges $v_{11}v_{13}$ and $v_{15}v_{16}$, we the following order is valid: $(v_{11}, v_{13}, v_{15}, v_{16}, v_7, v_8, v_9, v_{14}, v_4, v_6, v_{10}, v_3, v_{12}, v_3, v_{12}, v_1, v_2, v_5, v_0)$.

Third, we show that even if $x_1$ and $z_0$ are propagating to respectively $v_1$ and $v_0$, and $y_2$ is not, we need two PMUs to color $H_v$ (the argument for $(x_1$ and $y_2$) and $(y_2$ and $z_0$) is symmetric). The beginning of the propagation is given by the following order: $(v_0, v_1, v_3, v_5)$. There is no more possible propagation, therefore
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** The gadget $H_v$ for a vertex $v$.</figcaption></figure>

reduction from VERTEX COVER (see below) on 3-regular, planar graphs, which is $\mathcal{NP}$-complete [10] but admits a PTAS [1], and a 3/2-approximation [2].

### VERTEX COVER (VC)

**Input:** a graph $G = (V, E)$, some $k \in \mathbb{N}$.

**Question:** Is there a size-$k$ set $S \subseteq V$ covering $E$, i.e. $\forall e \in E \ e \cap S \neq \emptyset$?

**Construction 1** For a given cubic planar graph $G = (V, E)$ with $n$ vertices, we construct a graph $G'$ as follows:

- For each $v \in V$, construct $H_v$ (see Figure 3).

- For each $v \in V$ with $N_G(v) = \{x, y, z\}$, connect $H_x$ to $H_v$ with the edge $v_1x_1$, $H_y$ to $H_v$ with $v_2y_2$ and $H_z$ to $H_v$ with $v_0z_0$.

The graph $G'$ is clearly cubic and planar and Construction 4 is applied in polynomial time. The construction is linear in $n$ and $k$.

**Lemma 2.** The gadget $H_v$ needs at least one PMU to be fully colored: if $x_1, y_2$ and $z_0$ are propagating respectively to $v_1, v_2$ and $v_0$, then one PMU is sufficient; otherwise two PMUs are needed to fully color $H_v$.

*Proof.* First, if $x_1, y_2$ and $z_0$ are propagating respectively to $v_1, v_2$ and $v_0$, then, after application of RULE $R_2$, $c(v_0) = c(v_1) = c(v_2) = 1$. Thus this is the beginning of a valid order: $(v_0, v_1, v_2, v_3, v_5, v_4, v_6, v_7, v_{12}, v_9, v_{10})$. There is no more possible propagation, it is necessary to assign a new PMU. If we place it on the edge $v_{14}v_{16}$, the remainder of a valid order for $H_v$ is: $(v_{14}, v_{16}, v_{11}, v_8, v_{13}, v_{15}, v_{16})$.

Second, we show that $H_v$ may be colored by two PMUs in every case. If PMUs are assigned to the edges $v_{11}v_{13}$ and $v_{15}v_{16}$, we the following order is valid: $(v_{11}, v_{13}, v_{15}, v_{16}, v_7, v_8, v_9, v_{14}, v_4, v_6, v_{10}, v_3, v_{12}, v_3, v_{12}, v_1, v_2, v_5, v_0)$.

Third, we show that even if $x_1$ and $z_0$ are propagating to respectively $v_1$ and $v_0$, and $y_2$ is not, we need two PMUs to color $H_v$ (the argument for $(x_1$ and $y_2$) and $(y_2$ and $z_0$) is symmetric). The beginning of the propagation is given by the following order: $(v_0, v_1, v_3, v_5)$. There is no more possible propagation, therefore
we have to put one more PMU. As more than two uncolored vertices remain, so we have to initiate propagation with this PMU. So the potential edges are $v_6v_{12}$, $v_4v_2$, $v_6v_9$ or $v_{10}v_{12}$. By exhaustive search, we find that it is impossible to color $H_v$ with only PMU on any one of these edges. □

**Theorem 1.** POWER EDGE SET remains $\mathcal{NP}$-complete on planar cubic graphs.

*Proof.* Let $G'$ be the graph obtained by using Construction 4 on $G = (V, E)$, a cubic planar graph. We show that $G$ has a size-$k$ vertex cover iff POWER EDGE SET has a solution of size $n + k$ on $G'$. Clearly, POWER EDGE SET is in $\mathcal{NP}$.

“⇒”: With a size-$k$ vertex cover $S$ for $G$, we build a power edge set $S'$ for $G'$:

$$S' := \bigcup_{v \in S} \{v_{11}v_{16}, v_{13}v_{15}\} \cup \bigcup_{v \in V \setminus S} \{v_{14}v_{16}\}$$

Then, $|S'| = n + k$ and, by Lemma 2, all vertices of $G'$ are colored by $S'$.

“↔”: Suppose that $G'$ is colored with $n + k$ PMUs. By Lemma 2, there is at least one PMU on each gadget. Further, if a gadget $H_v$ is colored with a single PMU, then every $H_x$ with $x \in N_G(v)$ is colored with two PMUs inside (by Lemma 2). Then, $\{v | H_v$ admits two PMUs$\}$ is a vertex cover for $G$. □

# 3 Parameterized Hardness

In what follows, we introduce parameterized versions of our problems and recall the notion of parameterized reduction. Using known results for DOMINATING SET, we deduce hardness results for POWER EDGE SET and ZERO FORCING SET. First, we recall the parameterized DOMINATING SET problem.

**DOMINATING SET (DS)**

**Input:** a graph $G = (V, E)$, some $k \in \mathbb{N}^*$

**Question:** Does $G$ have a size-$k$ dominating set?

**Parameter:** $k$

We obtain hardness results for a restricted version of our problems, when a precoloring exists on a particular set of vertices.

**PRECOLORED ZERO FORCING SET/PRECOLORED POWER EDGE SET**

**Input:** a graph $G = (V, E)$, a set $B \subseteq V$, some $c: V \to \{0, 1\}$ with $c^{-1}(1) = B$, and an integer $k$

**Question:** Is there a set $S' \subseteq V$ (resp. $S' \subseteq E$) of size $k$ such that $B \cup S'$ (resp. $B \cup \bigcup_{e \in S'} e$) is a zero forcing set for $G$?

**Parameter:** $k$

We prove the hardness using a parameterized reduction from DOMINATING SET. First, we introduce a gadget which allows to propagate a coloration, but only in one direction. It is called "check-valve".
we have to put one more PMU. As more than two uncolored vertices remain, so we have to initiate propagation with this PMU. So the potential edges are $v_6v_{12}$, $v_4v_2$, $v_6v_9$ or $v_{10}v_{12}$. By exhaustive search, we find that it is impossible to color $H_v$ with only PMU on any one of these edges. □

**Theorem 1.** POWER EDGE SET remains $\mathcal{NP}$-complete on planar cubic graphs.

*Proof.* Let $G'$ be the graph obtained by using Construction 4 on $G = (V, E)$, a cubic planar graph. We show that $G$ has a size-$k$ vertex cover iff POWER EDGE SET has a solution of size $n + k$ on $G'$. Clearly, POWER EDGE SET is in $\mathcal{NP}$.

“⇒”: With a size-$k$ vertex cover $S$ for $G$, we build a power edge set $S'$ for $G'$:

$$S' := \bigcup_{v \in S} \{v_{11}v_{16}, v_{13}v_{15}\} \cup \bigcup_{v \in V \setminus S} \{v_{14}v_{16}\}$$

Then, $|S'| = n + k$ and, by Lemma 2, all vertices of $G'$ are colored by $S'$.

“↔”: Suppose that $G'$ is colored with $n + k$ PMUs. By Lemma 2, there is at least one PMU on each gadget. Further, if a gadget $H_v$ is colored with a single PMU, then every $H_x$ with $x \in N_G(v)$ is colored with two PMUs inside (by Lemma 2). Then, $\{v | H_v$ admits two PMUs$\}$ is a vertex cover for $G$. □

# 3 Parameterized Hardness

In what follows, we introduce parameterized versions of our problems and recall the notion of parameterized reduction. Using known results for DOMINATING SET, we deduce hardness results for POWER EDGE SET and ZERO FORCING SET. First, we recall the parameterized DOMINATING SET problem.

## DOMINATING SET (DS)

**Input:** a graph $G = (V, E)$, some $k \in \mathbb{N}^*$

**Question:** Does $G$ have a size-$k$ dominating set?

**Parameter:** $k$

We obtain hardness results for a restricted version of our problems, when a precoloring exists on a particular set of vertices.

## PRECOLORED ZERO FORCING SET/PRECOLORED POWER EDGE SET

**Input:** a graph $G = (V, E)$, a set $B \subseteq V$, some $c: V \to \{0, 1\}$ with $c^{-1}(1) = B$, and an integer $k$

**Question:** Is there a set $S' \subseteq V$ (resp. $S' \subseteq E$) of size $k$ such that $B \cup S'$ (resp. $B \cup \bigcup_{e \in S'} e$) is a zero forcing set for $G$?

**Parameter:** $k$

We prove the hardness using a parameterized reduction from DOMINATING SET. First, we introduce a gadget which allows to propagate a coloration, but only in one direction. It is called "check-valve".
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** The check-valve $C_{x,y}$</figcaption></figure>

**Definition 2 (Check-valve).** A check-valve $C_{x,y}$ from $x$ to $y$ is a graph $G = (V, E)$, with $V = \{x, y, x_1, x_2, x_3, x_4\}$ and $E = \{xx_1, xx_2, x_1x_3, x_1x_4, x_2x_4, x_3y, x_4y\}$, with a coloring function $c: V \to \mathbb{N}$, such that $c(x) = c(x_1) = 1$ and all other vertices are colored by 0. A check-valve $C_{x,y}$ is illustrated on Figure 4.

**Observation 2** Let $C_{x,y}$ be a check-valve inserted between two vertices $a$ and $b$, depicted by Figure 4. Then:

1. If $c(a) = 1$ then $c(b) = 1$ after exhaustive application of RULE $R_2$.

2. If $c(b) = 1$, and $c(a) = 0$, then $c(a)$ is still 0 after exhaustive application of RULE $R_2$, and it is necessary to add a PMU in order to have $c(a) = 1$.

**Construction 2** Let $xy$ be an edge such that $c(x) = 1$ and $c(y) = 0$, we construct the gadget $C_{xy}$: we add vertices $x_1, x_2, x_3$ and $x_4$ and we add edges $xx_1, x_1x_2, x_3y, yx_4, x_4x_2$ and $x_2x$. Notice that $xy$ is deleted.

**Construction 3** For given $G = (V, E)$, construct $G' = (V', E')$ as follows:

1. For all $x \in V$, build $J_x$ depicted in Figure 5, containing a core graph $((E_x, R_x, V_x, x_1, x_2, x_3, x_4), \{E_x x_3, E_x x_4, E_x V_x, x_1 x_3, x_2 x_4, R_x x_1, R_x x_2, R_x V_x\})$ with precolored vertices $V_x$, $x_3$ and $x_4$, and outgoing check-valves: $d_G(x)$ many $C_{x_1^{s_i}, x_2^{s_i}}$ connected to $E_x$, and $n$ many $C_{x_1^{s_i}, x_2^{s_i}}$ connected to $R_x$.

2. For all $v_i \in N(x)$, add edges $x_i^2 R_{v_i}$ with $x_i^2 \in J_x$ and $R_{v_i} \in J_{v_i}$.

3. For all $s_i \in V$, add edges $x_i^2 V_{s_i}$ with $x_i^2 \in J_x$ and $V_{s_i} \in J_{s_i}$.

**Lemma 3.** For all $x \in V$, if $c(E_x) = 1$ then, after exhaustive application of RULE $R_2$, $c(J_x) = 1$ and $c(R_x) = 1$ for all $v \in N(x)$.

*Proof.* If $V = \{s_1, \dots, s_n\}$ and $N(x) = \{v_1, \dots, v_t\}$, then the following sequence is a valid order: $(E_x, x_1, x_2, R_x, x_1^2, \dots, x_{s_1}^2, x_{v_1}^2, \dots, x_{v_t}^2, R_{v_1}, \dots, R_{v_t})$. $\square$

**Lemma 4.** Let $c(R_x) = 1$ for all $x \in V$. Then, after exhaustive application of RULE $R_2$, $G'$ becomes fully colored.

*Proof.* Clearly, all vertices in $N(V_x) \setminus \{E_x\}$ are colored by $R_x$ for all $x \in V$. Then, $E_x$ is colored by $V_x$. By Lemma 3, $c(E_x) = 1$ leads to $J_x$ being fully colored. As $V' = \bigcup_{z \in V} V(J_z)$, $G'$ becomes fully colored. $\square$

**Theorem 2.** PRECOLORED ZERO FORCING SET and PRECOLORED POWER EDGE SET are $W[2]$-hard wrt. the solution size $k$.
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** The check-valve $C_{x,y}$</figcaption></figure>

**Definition 2 (Check-valve).** A check-valve $C_{x,y}$ from $x$ to $y$ is a graph $G = (V, E)$, with $V = \{x, y, x_1, x_2, x_3, x_4\}$ and $E = \{xx_1, xx_2, x_1x_3, x_1x_4, x_2x_4, x_3y, x_4y\}$, with a coloring function $c: V \to \mathbb{N}$, such that $c(x) = c(x_1) = 1$ and all other vertices are colored by 0. A check-valve $C_{x,y}$ is illustrated on Figure 4.

**Observation 2** Let $C_{x,y}$ be a check-valve inserted between two vertices $a$ and $b$, depicted by Figure 4. Then:

1. If $c(a) = 1$ then $c(b) = 1$ after exhaustive application of RULE $R_2$.

2. If $c(b) = 1$, and $c(a) = 0$, then $c(a)$ is still 0 after exhaustive application of RULE $R_2$, and it is necessary to add a PMU in order to have $c(a) = 1$.

**Construction 2** Let $xy$ be an edge such that $c(x) = 1$ and $c(y) = 0$, we construct the gadget $C_{xy}$: we add vertices $x_1, x_2, x_3$ and $x_4$ and we add edges $xx_1, x_1x_2, x_3y, yx_4, x_4x_2$ and $x_2x$. Notice that $xy$ is deleted.

**Construction 3** For given $G = (V, E)$, construct $G' = (V', E')$ as follows:

1. For all $x \in V$, build $J_x$ depicted in Figure 5, containing a core graph $\{(E_x, R_x, V_x, x_1, x_2, x_3, x_4), \{E_x x_3, E_x x_4, E_x V_x, x_1 x_3, x_2 x_4, R_x x_1, R_x x_2, R_x V_x\})$ with precolored vertices $V_x$, $x_3$ and $x_4$, and outgoing check-valves: $d_G(x)$ many $C_{x_1^{s_i}, x_2^{s_i}}$ connected to $E_x$, and $n$ many $C_{x_1^{s_i}, x_2^{s_i}}$ connected to $R_x$.

2. For all $v_i \in N(x)$, add edges $x_i^2 R_{v_i}$ with $x_i^2 \in J_x$ and $R_{v_i} \in J_{v_i}$.

3. For all $s_i \in V$, add edges $x_i^2 V_{s_i}$ with $x_i^2 \in J_x$ and $V_{s_i} \in J_{s_i}$.

**Lemma 3.** For all $x \in V$, if $c(E_x) = 1$ then, after exhaustive application of RULE $R_2$, $c(J_x) = 1$ and $c(R_x) = 1$ for all $v \in N(x)$.

*Proof.* If $V = \{s_1, \dots, s_n\}$ and $N(x) = \{v_1, \dots, v_t\}$, then the following sequence is a valid order: $(E_x, x_1, x_2, R_x, x_1^2, \dots, x_{s_1}^2, x_{v_1}^2, \dots, x_{v_t}^2, R_{v_1}, \dots, R_{v_t})$. $\square$

**Lemma 4.** Let $c(R_x) = 1$ for all $x \in V$. Then, after exhaustive application of RULE $R_2$, $G'$ becomes fully colored.

*Proof.* Clearly, all vertices in $N(V_x) \setminus \{E_x\}$ are colored by $R_x$ for all $x \in V$. Then, $E_x$ is colored by $V_x$. By Lemma 3, $c(E_x) = 1$ leads to $J_x$ being fully colored. As $V' = \bigcup_{z \in V} V(J_z)$, $G'$ becomes fully colored. $\square$

**Theorem 2.** PRECOLORED ZERO FORCING SET and PRECOLORED POWER EDGE SET are $W[2]$-hard wrt. the solution size $k$.
colored (see Case 1). Consequently, if $c(E_{v_i}) = 1$ then $c(w) = 1$ for some $w \in J_{v_i}$ contradicting $S$ not being a dominating set.

Thus $S$ is a dominating set of $G$. Further, Construction 3 can be carried out in polynomial time and $|S| = |S'|$, yielding the desired result. $\square$

# 4 Hardness according to other complexity hypotheses

## 4.1 Lower Bounds for Exact and FPT Algorithms

In this section, we propose some negative results for POWER EDGE SET concerning subexponential-time and parameterized algorithms under $\mathcal{ETH}$ (see [15]).

Since the polynomial-time transformation given in Theorem 1 is linear in the number of vertices and VERTEX COVER does not admit a $2^{o(\sqrt{n})}$-time algorithm, even on 3-regular, planar graphs, there is also no $2^{o(\sqrt{n})}$-time algorithm for POWER EDGE SET in cubic planar graphs.

Moreover, since $k \le n$, a $2^{o(k)}n^c$-time algorithm directly implies a $2^{o(n)}$-time algorithm for VERTEX COVER. However, we know VERTEX COVER does not admit such an algorithm (even in the planar case) unless the $\mathcal{ETH}$ fails [17]. Therefore, we obtain the following results.

**Corollary 1.** *Assuming* $\mathcal{ETH}$, POWER EDGE SET does not admit a $2^{o(\sqrt{n})}$-time algorithm, even in planar cubic graphs, nor a $2^{o(k)}n^{O(1)}$-time algorithm, even on planar graphs.

Based on the previous complexity result, it is clear that POWER EDGE SET parameterized by $\Delta$ (the maximum degree of the graph) is not in $\mathcal{XP}$.

## 4.2 Hardness according to UGC

In the following, we propose an $L$-reduction from VERTEX COVER in 3-uniform hypergraphs. An $L$-reduction (see [19]) between problems $\Pi$ and $\Pi'$ is defined as follows: let $f: \Pi \to \Pi'$ and $g$ be polynomial-time computable functions such that, for all $x \in \Pi$ and each feasible solution $y'$ for $f(x)$, $g(y')$ is a feasible solution for $x$. Moreover, there are constants $\alpha_1, \alpha_2 > 0$ such that:

1. $OPT_{\Pi'}(f(x)) \le \alpha_1 OPT_{\Pi}(x)$ and

2. $|val_{\Pi}(g(y')) - OPT_{\Pi}(x)| \le \alpha_2|val_{\Pi'}(y') - OPT_{\Pi'}(f(x))|$.

Even on 3-uniform graphs, VERTEX COVER is hard to approximate within a factor less than $2 - \epsilon$ for all $\epsilon > 0$ (assuming $P \ne \mathcal{NP}$), even if each vertex appears in at most three edges [6]. It is also hard to approximate within a factor less than $3 - \epsilon$ for all $\epsilon > 0$ (assuming $\mathcal{UGC}$) [22].

**Construction 4** Let $G = (V, E)$ be a cubic planar hypergraph. Build $G'$ by

- for each $v \in V$ constructing the gadget $H_v$ (see Figure 3),

- for each $xyz \in E$ constructing the gadget $J_{xyz}$ (see Figure 6), and

- for each $e = xyz \in E$ connecting $J_{xyz}$ to $H_x$ (resp. $H_y, H_z$) by the edge $e_0x_0$ (resp. $e_1y_1, e_2z_2$).
colored (see Case 1). Consequently, if $c(E_{v_i}) = 1$ then $c(w) = 1$ for some $w \in J_{v_i}$ contradicting $S$ not being a dominating set.

Thus $S$ is a dominating set of $G$. Further, Construction 3 can be carried out in polynomial time and $|S| = |S'|$, yielding the desired result. $\square$

# 4 Hardness according to other complexity hypotheses

## 4.1 Lower Bounds for Exact and FPT Algorithms

In this section, we propose some negative results for POWER EDGE SET concerning subexponential-time and parameterized algorithms under $\mathcal{ETH}$ (see [15]).

Since the polynomial-time transformation given in Theorem 1 is linear in the number of vertices and VERTEX COVER does not admit a $2^{o(\sqrt{n})}$-time algorithm, even on 3-regular, planar graphs, there is also no $2^{o(\sqrt{n})}$-time algorithm for POWER EDGE SET in cubic planar graphs.

Moreover, since $k \le n$, a $2^{o(k)}n^c$-time algorithm directly implies a $2^{o(n)}$-time algorithm for VERTEX COVER. However, we know VERTEX COVER does not admit such an algorithm (even in the planar case) unless the $\mathcal{ETH}$ fails [17]. Therefore, we obtain the following results.

**Corollary 1.** *Assuming* $\mathcal{ETH}$, POWER EDGE SET does not admit a $2^{o(\sqrt{n})}$-time algorithm, even in planar cubic graphs, nor a $2^{o(k)}n^{O(1)}$-time algorithm, even on planar graphs.

Based on the previous complexity result, it is clear that POWER EDGE SET parameterized by $\Delta$ (the maximum degree of the graph) is not in $\mathcal{XP}$.

## 4.2 Hardness according to UGC

In the following, we propose an $L$-reduction from VERTEX COVER in 3-uniform hypergraphs. An $L$-reduction (see [19]) between problems $\Pi$ and $\Pi'$ is defined as follows: let $f: \Pi \to \Pi'$ and $g$ be polynomial-time computable functions such that, for all $x \in \Pi$ and each feasible solution $y'$ for $f(x)$, $g(y')$ is a feasible solution for $x$. Moreover, there are constants $\alpha_1, \alpha_2 > 0$ such that:

1. $OPT_{\Pi'}(f(x)) \le \alpha_1 OPT_{\Pi}(x)$ and

2. $|val_{\Pi}(g(y')) - OPT_{\Pi}(x)| \le \alpha_2|val_{\Pi'}(y') - OPT_{\Pi'}(f(x))|$.

Even on 3-uniform graphs, VERTEX COVER is hard to approximate within a factor less than $2 - \epsilon$ for all $\epsilon > 0$ (assuming $P \ne \mathcal{NP}$), even if each vertex appears in at most three edges [6]. It is also hard to approximate within a factor less than $3 - \epsilon$ for all $\epsilon > 0$ (assuming $\mathcal{UGC}$) [22].

**Construction 4** Let $G = (V, E)$ be a cubic planar hypergraph. Build $G'$ by

- for each $v \in V$ constructing the gadget $H_v$ (see Figure 3),

- for each $xyz \in E$ constructing the gadget $J_{xyz}$ (see Figure 6), and

- for each $e = xyz \in E$ connecting $J_{xyz}$ to $H_x$ (resp. $H_y, H_z$) by the edge $e_0x_0$ (resp. $e_1y_1, e_2z_2$).
<figure><img src="image_6.png" /><figcaption>Fig. 6. The gadget $J_{xyz}$ for an edge $xyz$.</figcaption></figure>

Note that $x_i \neq y_i$ for all $i$ but, for distinct $i$ and $j$, $x_i$ can be equal to $x_j$ or $y_j$.

**Lemma 5.** The gadget $J_{xyz}$ may be colored with only one PMU if at least one among $x_1, y_2$ or $z_0$ is propagating to respectively $e_1, e_2$ or $e_0$. Further, any zero forcing set contains a vertex of $J_{xyz}$.

*Proof.* By symmetry, we assume w.l.o.g. that $x_1$ is propagating to $e_1$. First, assigning a PMU to $e_3e_6$ we get the following valid order: $(e_1, e_3, e_6, e_4, e_0, e_5, e_2)$. Second, even if $e_0, e_1$ and $e_2$ are colored by propagation from outside $J_{xyz}$, the propagation stops unless a PMU is assigned to an edge of $J_{xzy}$. $\square$

**Theorem 3.** *Under UGC, POWER EDGE SET on cubic graphs cannot be approximated to within a factor better than 13/11*

*Proof.* Let $G'$ be the result of applying Figure 4 to a hypergraph $G = (V, E)$. We show that $G$ has a size-$k$ vertex cover iff POWER EDGE SET has a solution of size $k + 2n$ on $G'$.

“⇒”: Let $S$ be a size-$k$ vertex cover for $G$. We build a solution $S'$ for $G'$:

$$S' := \bigcup_{v \in S} (\{v_{11}v_{16}\} \cup \{v_{13}v_{15}\}) \cup \bigcup_{v \in V \setminus S} \{v_{14}v_{16}\} \cup \bigcup_{xzy \in E} \begin{cases} \{e_3e_6\} & \text{if } x \in S \\ \{e_4e_6\} & \text{if } y \in S \\ \{e_5e_6\} & \text{if } z \in S \end{cases}$$

By Lemma 5, $S'$ is a power edge set for $G'$ and $|S'| = k + 2n$.

“↔”: Assume that $G'$ possesses $2n+k$ PMUs such that all vertices are colored. Lemma 2 and Lemma 5 state that it is impossible to color a gadget without any PMU inside, so there is at least one PMU on each gadget $H$ and $J$. If there is more than one PMU on a gadget $J$, we count it as if it is inside any adjacent gadget $H$. If a gadget $H_v$ is colored by a single PMU, it means that, for each hyperedge containing $v$, there is at least one $H_x$ with $x$ in this hyper-edge, which counts two PMUs. Thus, $X := \{v \mid H_v \text{ admits two PMUs}\}$ is a vertex-cover. Suppose that more than $k$ gadgets have at least two PMUs. Then, there is at least one gadget without any PMU, contradicting Lemma 5. Thus, $|S| \leq k$.

Finally, to show that Figure 4 is an $L$-reduction, let $f$ be a function transforming any 3-uniform instance $I$ of VERTEX COVER into an instance $I'$ of POWER EDGE SET as above, let $S'$ be any feasible solution for $I'$, and let $g$ be the function that transforms $S'$ into a solution $S$ that contains one or two edges per gadget $H_v$ and one per gadget $J_{xyz}$, and then outputs the set of vertices
<figure><img src="image_6.png" /><figcaption>**Fig. 6.** The gadget $J_{xyz}$ for an edge $xyz$.</figcaption></figure>

Note that $x_i \neq y_i$ for all $i$ but, for distinct $i$ and $j$, $x_i$ can be equal to $x_j$ or $y_j$.

**Lemma 5.** The gadget $J_{xyz}$ may be colored with only one PMU if at least one among $x_1, y_2$ or $z_0$ is propagating to respectively $e_1, e_2$ or $e_0$. Further, any zero forcing set contains a vertex of $J_{xyz}$.

*Proof.* By symmetry, we assume w.l.o.g. that $x_1$ is propagating to $e_1$. First, assigning a PMU to $e_3e_6$ we get the following valid order: $(e_1, e_3, e_6, e_4, e_0, e_5, e_2)$. Second, even if $e_0, e_1$ and $e_2$ are colored by propagation from outside $J_{xyz}$, the propagation stops unless a PMU is assigned to an edge of $J_{xzy}$. $\square$

**Theorem 3.** *Under UGC, POWER EDGE SET on cubic graphs cannot be approximated to within a factor better than 13/11*

*Proof.* Let $G'$ be the result of applying Figure 4 to a hypergraph $G = (V, E)$. We show that $G$ has a size-$k$ vertex cover iff POWER EDGE SET has a solution of size $k + 2n$ on $G'$.

“⇒”: Let $S$ be a size-$k$ vertex cover for $G$. We build a solution $S'$ for $G'$:

$$S' := \bigcup_{v \in S} (\{v_{11}v_{16}\} \cup \{v_{13}v_{15}\}) \cup \bigcup_{v \in V \setminus S} \{v_{14}v_{16}\} \cup \bigcup_{xzy \in E} \begin{cases} \{e_3e_6\} & \text{if } x \in S \\ \{e_4e_6\} & \text{if } y \in S \\ \{e_5e_6\} & \text{if } z \in S \end{cases}$$

By Lemma 5, $S'$ is a power edge set for $G'$ and $|S'| = k + 2n$.

“⇔”: Assume that $G'$ possesses $2n+k$ PMUs such that all vertices are colored. Lemma 2 and Lemma 5 state that it is impossible to color a gadget without any PMU inside, so there is at least one PMU on each gadget $H$ and $J$. If there is more than one PMU on a gadget $J$, we count it as if it is inside any adjacent gadget $H$. If a gadget $H_v$ is colored by a single PMU, it means that, for each hyperedge containing $v$, there is at least one $H_x$ with $x$ in this hyper-edge, which counts two PMUs. Thus, $X := \{v \mid H_v \text{ admits two PMUs}\}$ is a vertex-cover. Suppose that more than $k$ gadgets have at least two PMUs. Then, there is at least one gadget without any PMU, contradicting Lemma 5. Thus, $|S| \leq k$.

Finally, to show that Figure 4 is an $L$-reduction, let $f$ be a function transforming any 3-uniform instance $I$ of VERTEX COVER into an instance $I'$ of POWER EDGE SET as above, let $S'$ be any feasible solution for $I'$, and let $g$ be the function that transforms $S'$ into a solution $S$ that contains one or two edges per gadget $H_v$ and one per gadget $J_{xyz}$, and then outputs the set of vertices
<figure><img src="image_7.png" /><figcaption>Fig. 7. An interval graph (7a), with its interval representation (7b), a perfect path decomposition of this graph (7c) and its bag partition according to Definition 4 (7d).</figcaption></figure>

v for which S assigns two PMUs to $H_v$. First, the above argument shows that $g(S')$ is a feasible solution for $I'$.

Second, by construction, $OPT(I') = OPT(I) + n + m$. Let S be a solution to I. Then, we have $m \le \sum_{v \in S} d_G(v)$, and $d_G(v) \le 3$. We obtain $m \le 3OPT(I)$ as $|S| = OPT(I)$. Moreover, $m \le n$. Since each vertex of I appears in at most three hyperedges of I, at least one in seven vertices has to be in a vertex cover of G, implying $n/7 \le OPT(I)$. Thus, $OPT(I') \le 11OPT(I)$

Third, by construction of g, we have

$$val(g(S')) \le val(S') - n - m \le val(S') - OPT(I') + OPT(I)$$

Thus, we constructed an L-reduction with $\alpha_1 = 11$ and $\alpha_2 = 1$.

Assuming $\mathcal{UGC}$, VERTEX COVER on 3-uniform hypergraphs is hard to approximate to a factor $3 - \epsilon$ [22], thus yielding to the desired result:

$$ 
\begin{aligned}
|S'| & \ge |g(S')| + OPT(I') - OPT(I) \\
& \ge (3 - \epsilon)OPT(I) + OPT(I') - OPT(I) \\
& \ge \frac{13}{11}OPT(I')
\end{aligned}
\qquad \square
$$

## 5 ZFS on Proper Interval Graphs

*Preliminaries.* A graph G is an interval graph if it is the intersection graph of a family of intervals on the real line. Each interval is represented by a vertex of G and an intersection between two intervals is represented by an edge between the corresponding vertices (see Figure 7). G is called proper interval if it has an interval representation in which no interval is properly contained in another. In the following, we use perfect path decompositions to solve POWER EDGE SET on proper interval graphs.

**Definition 3.** A path decomposition $\mathcal{D}$ of a graph G = (V, E) is a sequence $(X_i)_{i=1...|\mathcal{D}|}$ of subsets of V (called bags), verifying the following properties:
<figure><img src="image_7.png" /><figcaption>**Fig. 7.** An interval graph (7a), with its interval representation (7b), a perfect path decomposition of this graph (7c) and its bag partition according to Definition 4 (7d).</figcaption></figure>

v for which S assigns two PMUs to $H_v$. First, the above argument shows that $g(S')$ is a feasible solution for $I'$.

Second, by construction, $OPT(I') = OPT(I) + n + m$. Let S be a solution to I. Then, we have $m \le \sum_{v \in S} d_G(v)$, and $d_G(v) \le 3$. We obtain $m \le 3OPT(I)$ as $|S'| = OPT(I)$. Moreover, $m \le n$. Since each vertex of I appears in at most three hyperedges of I, at least one in seven vertices has to be in a vertex cover of G, implying $n/7 \le OPT(I)$. Thus, $OPT(I') \le 11OPT(I)$

Third, by construction of g, we have

$$val(g(S')) \le val(S') - n - m \le val(S') - OPT(I') + OPT(I)$$

Thus, we constructed an L-reduction with $\alpha_1 = 11$ and $\alpha_2 = 1$.

Assuming $\mathcal{UGC}$, VERTEX COVER on 3-uniform hypergraphs is hard to approximate to a factor $3 - \epsilon$ [22], thus yielding to the desired result:

$$ 
\begin{aligned}
|S'| & \ge |g(S')| + OPT(I') - OPT(I) \\
& \ge (3 - \epsilon)OPT(I) + OPT(I') - OPT(I) \\
& \ge \frac{13}{11}OPT(I')
\end{aligned}
\qquad \square
$$

# 5 ZFS on Proper Interval Graphs

*Preliminaries.* A graph G is an interval graph if it is the intersection graph of a family of intervals on the real line. Each interval is represented by a vertex of G and an intersection between two intervals is represented by an edge between the corresponding vertices (see Figure 7). G is called proper interval if it has an interval representation in which no interval is properly contained in another. In the following, we use perfect path decompositions to solve POWER EDGE SET on proper interval graphs.

**Definition 3.** A path decomposition $\mathcal{D}$ of a graph G = (V, E) is a sequence $(X_i)_{i=1...|\mathcal{D}|}$ of subsets of V (called bags), verifying the following properties:
(a) for each $xy \in E$, there is some $X_i$ with $x, y \in X_i$ (each edge is in a bag),
(b) for $i \le j \le k$, $X_i \cap X_k \subseteq X_j$ (bags containing any $v \in V$ are consecutive).
$\mathcal{D}$ is called perfect if the number of bags and their sizes are minimal under (a)
and (b). The pathwidth of $\mathcal{D}$ is the size of the largest $X_i$ minus one.

**Lemma 6.** If $G$ is connected, then $X_i \cap X_{i-1} \neq \emptyset$ for all $i > 1$.

*Proof.* Towards a contradiction, assume that $X_i \cap X_{i-1} = \emptyset$. Then, by Definition 3(b), $A := \bigcup_{1 \le k \le i-1} X_k$ and $B := \bigcup_{i \le l} X_l$ are disjoint. Since $G$ is connected, there is an edge $xy$ between $A$ and $B$, but no bag contains both $x$ and $y$, contradicting Definition 3(a). $\square$

**Lemma 7.** Let $G$ be an interval graph. A perfect path decomposition $\mathcal{D}$ of $G$ can be computed in linear time and each bag of $\mathcal{D}$ is a maximal clique in $G$.

*Proof.* Being an interval graph, $G$ admits a linear order of its maximal cliques such that, for each vertex $v$, all maximal cliques containing $v$ are consecutive [9] and this order can be computed in $O(n+m)$ time [13]. Such a "clique path" naturally corresponds to a perfect path decomposition and we know that vertices of each bags induce maximal cliques. In a clique path, the size and the number of bags are minimal. $\square$

*The Algorithm*. In the following, $G$ is a connected proper interval graph and $\mathcal{D} = (X_1, \dots, X_\ell)$ is a perfect path decomposition of $G$. We show that it is possible to apply RULE $R_2$ once per maximal clique $X_i$ in interval graphs. The central concept is a partition of the bags of $\mathcal{D}$ into four sets.

**Definition 4 (Bag partition, see Figure 7).** Let $X_i$ be a bag in a perfect path decomposition of an interval graph.

<figure><img src="image_8.png" /></figure>

- IO (Inside Only) is the set $X_i \setminus (X_{i-1} \cup X_{i+1})$.

- LO (Left Only) is the set $X_i \cap X_{i-1} \setminus X_{i+1}$.

- RO (Right Only) is the set $X_i \cap X_{i+1} \setminus X_{i-1}$.

- LR (Left Right), contains all remaining vertices of $X_i$.

Note that $RO(X_i)$ and $RO(X_j)$ are disjoint for $i \neq j$. Further, since $G$ is proper interval, $RO(X_i) \neq \emptyset$ for all $i < \ell$. Our algorithm will simply choose any vertex of $RO(X_i) \cup IO(X_i)$ for all $i$. This can clearly be done in linear time and we show that it is correct and optimal.

**Lemma 8.** Let $G$ be a connected interval graph and let $\mathcal{D} = (X_1, \dots, X_\ell)$ be a perfect path decomposition of $G$. Let $\bar{S}$ be a set intersecting each $RO(X_i)$ for all $1 \le i < \ell$ in exactly one vertex and intersecting $IO(X_\ell)$ in exactly one vertex. Then, $S := V \setminus \bar{S}$ is an optimal zero forcing set for $G$.

*Proof.* For each $i$, let $x_i$ be the $i^{th}$ vertex of $\bar{S}$, that is, $\bar{S} \cap (RO(X_i) \cup IO(X_i)) = \{x_i\}$ for each $X_i \in \mathcal{D}$. We show that the order $\sigma$ consisting of $S$ in any order followed by $(x_1, \dots, x_\ell)$ is valid for $S$. To this end, let $1 \le j < \ell$. Note that $IO(X_j) \cup LO(X_j) = ((X_j \setminus X_{j+1}) \cap X_{j-1}) \cup ((X_j \setminus X_{j+1}) \setminus X_{j+1}) = X_j \setminus X_{j+1}$. Thus, there is some $u \in IO(X_j) \cup LO(X_j)$ as otherwise, $X_j \subseteq X_{j+1}$ contradicting
(a) for each $xy \in E$, there is some $X_i$ with $x, y \in X_i$ (each edge is in a bag),
(b) for $i \le j \le k$, $X_i \cap X_k \subseteq X_j$ (bags containing any $v \in V$ are consecutive).
$\mathcal{D}$ is called perfect if the number of bags and their sizes are minimal under (a)
and (b). The pathwidth of $\mathcal{D}$ is the size of the largest $X_i$ minus one.

**Lemma 6.** If $G$ is connected, then $X_i \cap X_{i-1} \neq \emptyset$ for all $i > 1$.

*Proof.* Towards a contradiction, assume that $X_i \cap X_{i-1} = \emptyset$. Then, by Definition 3(b), $A := \cup_{1 \le k \le i-1} X_k$ and $B := \cup_{i \le l} X_l$ are disjoint. Since $G$ is connected, there is an edge $xy$ between $A$ and $B$, but no bag contains both $x$ and $y$, contradicting Definition 3(a). $\square$

**Lemma 7.** Let $G$ be an interval graph. A perfect path decomposition $\mathcal{D}$ of $G$ can be computed in linear time and each bag of $\mathcal{D}$ is a maximal clique in $G$.

*Proof.* Being an interval graph, $G$ admits a linear order of its maximal cliques such that, for each vertex $v$, all maximal cliques containing $v$ are consecutive [9] and this order can be computed in $O(n+m)$ time [13]. Such a "clique path" naturally corresponds to a perfect path decomposition and we know that vertices of each bags induce maximal cliques. In a clique path, the size and the number of bags are minimal. $\square$

*The Algorithm*. In the following, $G$ is a connected proper interval graph and $\mathcal{D} = (X_1, \dots, X_\ell)$ is a perfect path decomposition of $G$. We show that it is possible to apply RULE $R_2$ once per maximal clique $X_i$ in interval graphs. The central concept is a partition of the bags of $\mathcal{D}$ into four sets.

**Definition 4 (Bag partition, see Figure 7).** Let $X_i$ be a bag in a perfect path decomposition of an interval graph.

<figure><img src="image_8.png" /></figure>

- IO (Inside Only) is the set $X_i \setminus (X_{i-1} \cup X_{i+1})$.

- LO (Left Only) is the set $X_i \cap X_{i-1} \setminus X_{i+1}$.

- RO (Right Only) is the set $X_i \cap X_{i+1} \setminus X_{i-1}$.

- LR (Left Right), contains all remaining vertices of $X_i$.

Note that $RO(X_i)$ and $RO(X_j)$ are disjoint for $i \neq j$. Further, since $G$ is proper interval, $RO(X_i) \neq \emptyset$ for all $i < \ell$. Our algorithm will simply choose any vertex of $RO(X_i) \cup IO(X_i)$ for all $i$. This can clearly be done in linear time and we show that it is correct and optimal.

**Lemma 8.** Let $G$ be a connected interval graph and let $\mathcal{D} = (X_1, \dots, X_\ell)$ be a perfect path decomposition of $G$. Let $\bar{S}$ be a set intersecting each $RO(X_i)$ for all $1 \le i < \ell$ in exactly one vertex and intersecting $IO(X_\ell)$ in exactly one vertex. Then, $S := V \setminus \bar{S}$ is an optimal zero forcing set for $G$.

*Proof.* For each $i$, let $x_i$ be the $i^{th}$ vertex of $\bar{S}$, that is, $\bar{S} \cap (RO(X_i) \cup IO(X_i)) = \{x_i\}$ for each $X_i \in \mathcal{D}$. We show that the order $\sigma$ consisting of $S$ in any order followed by $(x_1, \dots, x_\ell)$ is valid for $S$. To this end, let $1 \le j < \ell$. Note that $IO(X_j) \cup LO(X_j) = ((X_j \setminus X_{j+1}) \cap X_{j-1}) \cup ((X_j \setminus X_{j+1}) \setminus X_{j+1}) = X_j \setminus X_{j+1}$. Thus, there is some $u \in IO(X_j) \cup LO(X_j)$ as otherwise, $X_j \subseteq X_{j+1}$ contradicting
D being perfect. Towards a contradiction, assume $N_G[u] \leq_{\sigma} x_j$, that is, there is some $v \in N_G[u]$ with $x_j <_{\sigma} v$. By construction of $\sigma$, there is a $k > j$ such that $v = x_k$. By construction of $\bar{S}$, we have $x_k \in IO(X_k) \cup RO(X_k)$, implying $x_k \notin X_{k-1}$ by definition of RO and IO. Further, since $ux_k$ is an edge of $G$, there is a bag $X_i$ containing both $u$ and $x_k$ and, since $u \in IO(X_j) \cup LO(X_j)$ we know $i \le j$. But then, $x_k$ occurs in $X_i$, not in $X_{k-1}$ but again in $X_k$, contradicting D being perfect. It remains to treat $x_\ell$, but since $x_\ell$ is the last vertex of $\sigma$, $N_G[u] \le_{\sigma} x_\ell$ for all $u \in N_G(x_\ell)$.

Finally, optimality of $S$ is implied by Lemma 1 as $|\bar{S}| = |D|$. $\square$

<figure><img src="image_9.png" /></figure>

**Theorem 4.** ZERO FORCING SET is solvable in $O(n+m)$ time on proper interval graphs.

# 6 Conclusion and perspectives

In this article, we investigated POWER EDGE SET and ZERO FORCING SET from the point of view of computational complexity. We obtained a series of negative results, refining the previous hardness results and excluding certain exact algorithms. On the positive side, we give a linear-time algorithm in case the input is a proper interval graph. Further research will be focused on developing efficient polynomial-time approximation algorithms, as well as considering more special cases and structural parameterizations.

# References

1. Baker, B.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of ACM 41(1), 153–180 (1994)

2. Bar-Yehuda, R., Even, S.: On Approximating a Vertex Cover for Planar Graphs. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. pp. 303–309 (1982)

3. Barioli, F., Barrett, W., Butler, S., Cioabă, S.M., Cvetković, D., Fallat, S.M., Godsil, C., Haemers, W., Hoghen, L., Mikkelson, R., et al.: Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications 428 (2008)

4. Cheng, X., Huang, X., Li, D., Wu, W., Du, D.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4), 202–208 (2003)

5. Darties, B., Chateau, A., Giroudeau, R., Weller, M.: Complexity and lowers bounds for power edge set problem. accepted Journal of Discrete Algorithms (2018)

6. Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing 34(5), 1129–1146 (2005)

7. Dorfling, M., Henning, M.A.: A note on power domination in grid graphs. Discrete Applied Mathematics 154(6), 1023–1027 (2006)

8. Fan, N., Watson, J.: Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming, pp. 371–383. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
D being perfect. Towards a contradiction, assume $N_G[u] \leq_{\sigma} x_j$, that is, there is some $v \in N_G[u]$ with $x_j <_{\sigma} v$. By construction of $\sigma$, there is a $k > j$ such that $v = x_k$. By construction of $\bar{S}$, we have $x_k \in IO(X_k) \cup RO(X_k)$, implying $x_k \notin X_{k-1}$ by definition of RO and IO. Further, since $ux_k$ is an edge of $G$, there is a bag $X_i$ containing both $u$ and $x_k$ and, since $u \in IO(X_j) \cup LO(X_j)$ we know $i \le j$. But then, $x_k$ occurs in $X_i$, not in $X_{k-1}$ but again in $X_k$, contradicting D being perfect. It remains to treat $x_\ell$, but since $x_\ell$ is the last vertex of $\sigma$, $N_G[u] \le_{\sigma} x_\ell$ for all $u \in N_G(x_\ell)$.

Finally, optimality of $S$ is implied by Lemma 1 as $|\bar{S}| = |D|$. $\square$

<figure><img src="image_9.png" /></figure>

**Theorem 4.** ZERO FORCING SET is solvable in $O(n+m)$ time on proper interval graphs.

# 6 Conclusion and perspectives

In this article, we investigated POWER EDGE SET and ZERO FORCING SET from the point of view of computational complexity. We obtained a series of negative results, refining the previous hardness results and excluding certain exact algorithms. On the positive side, we give a linear-time algorithm in case the input is a proper interval graph. Further research will be focused on developing efficient polynomial-time approximation algorithms, as well as considering more special cases and structural parameterizations.

# References

1. Baker, B.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of ACM 41(1), 153–180 (1994)

2. Bar-Yehuda, R., Even, S.: On Approximating a Vertex Cover for Planar Graphs. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. pp. 303–309 (1982)

3. Barioli, F., Barrett, W., Butler, S., Cioabă, S.M., Cvetković, D., Fallat, S.M., Godsil, C., Haemers, W., Hoghen, L., Mikkelson, R., et al.: Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications 428 (2008)

4. Cheng, X., Huang, X., Li, D., Wu, W., Du, D.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4), 202–208 (2003)

5. Darties, B., Chateau, A., Giroudeau, R., Weller, M.: Complexity and lowers bounds for power edge set problem. accepted Journal of Discrete Algorithms (2018)

6. Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing 34(5), 1129–1146 (2005)

7. Dorfling, M., Henning, M.A.: A note on power domination in grid graphs. Discrete Applied Mathematics 154(6), 1023–1027 (2006)

8. Fan, N., Watson, J.: Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming, pp. 371–383. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
9. Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. **15**(3), 835-855 (1965), https://projecteuclid.org:443/euclid.pjm/1102995572

10. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)

11. Gou, B.: Generalized integer linear programming formulation for optimal pmu placement. IEEE Transactions on Power Systems **23**(3), 1099-1104 (2008)

12. Guo, J., Niedermeier, R., Raible, D.: Improved algorithms and complexity results for power domination in graphs. Algorithmica **52**(2), 177-202 (2008)

13. Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Sciences **234**(1-2), 59-84 (2000)

14. Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM Journal on Discrete Mathematics **15**(4), 519-529 (2002)

15. Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences **63**(4), 512-530 (2001)

16. Li, Y., Thai, M.T., Wang, F., Yi, C., Wan, P., Du, D.: On greedy construction of connected dominating sets in wireless networks. Wireless Communications and Mobile Computing **5**(8), 927-932 (2005)

17. Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS **105**, 41-72 (2011)

18. Milosevic, B., Begovic, M.: Nondominated sorting genetic algorithm for optimal phasor maesurement placement. IEEE Power Engineering Review **22**(12), 61-61 (2002)

19. Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. **43**(3), 425-440 (1991)

20. Poirion, P., Toubaline, S., D'Ambrosio, C., Liberti, L.: The power edge set problem. Networks **68**(2), 104-120 (2016)

21. Simonetti, L., Salles da Cunha, A., Lucena, A.: The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm, pp. 162-169. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

22. Subhash, K., Oded, R.: Vertex cover might be hard to approximate to within 2-/spl epsiv. In: Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on. pp. 379-386. IEEE (2003)

23. Thai, M.T., Du, D.Z.: Connected dominating sets in disk graphs with bidirectional links. IEEE Communications Letters **10**(3), 138-140 (Mar 2006)

24. Toubaline, S., D'Ambrosio, C., Liberti, L., Poirion, P., Schieber, B., Shachnai, H.: Complexity and inapproximability results for the power edge set problem. Journal of Combinatorial Optimization **35**(3), 895-905 (2018)

25. Toubaline, S., Poirion, P., D'Ambrosio, C., Liberti, L.: Observing the State of a Smart Grid Using Bilevel Programming, pp. 364-376. Springer International Publishing, Cham (2015)

26. Yuill, W., Edwards, A., Chowdhury, S., Chowdhury, S.P.: Optimal pmu placement: A comprehensive literature review. In: 2011 IEEE Power and Energy Society General Meeting. pp. 1-8 (July 2011)
9. Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15(3), 835-855 (1965), https://projecteuclid.org:443/euclid.pjm/1102995572

10. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)

11. Gou, B.: Generalized integer linear programming formulation for optimal pmu placement. IEEE Transactions on Power Systems 23(3), 1099-1104 (2008)

12. Guo, J., Niedermeier, R., Raible, D.: Improved algorithms and complexity results for power domination in graphs. Algorithmica 52(2), 177-202 (2008)

13. Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Sciences 234(1-2), 59-84 (2000)

14. Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM Journal on Discrete Mathematics 15(4), 519-529 (2002)

15. Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences 63(4), 512-530 (2001)

16. Li, Y., Thai, M.T., Wang, F., Yi, C., Wan, P., Du, D.: On greedy construction of connected dominating sets in wireless networks. Wireless Communications and Mobile Computing 5(8), 927-932 (2005)

17. Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS 105, 41-72 (2011)

18. Milosevic, B., Begovic, M.: Nondominated sorting genetic algorithm for optimal phasor maesurement placement. IEEE Power Engineering Review 22(12), 61-61 (2002)

19. Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425-440 (1991)

20. Poirion, P., Toubaline, S., D'Ambrosio, C., Liberti, L.: The power edge set problem. Networks 68(2), 104-120 (2016)

21. Simonetti, L., Salles da Cunha, A., Lucena, A.: The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm, pp. 162-169. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

22. Subhash, K., Oded, R.: Vertex cover might be hard to approximate to within 2-/spl epsiv. In: Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on. pp. 379-386. IEEE (2003)

23. Thai, M.T., Du, D.Z.: Connected dominating sets in disk graphs with bidirectional links. IEEE Communications Letters 10(3), 138-140 (Mar 2006)

24. Toubaline, S., D'Ambrosio, C., Liberti, L., Poirion, P., Schieber, B., Shachnai, H.: Complexity and inapproximability results for the power edge set problem. Journal of Combinatorial Optimization 35(3), 895-905 (2018)

25. Toubaline, S., Poirion, P., D'Ambrosio, C., Liberti, L.: Observing the State of a Smart Grid Using Bilevel Programming, pp. 364-376. Springer International Publishing, Cham (2015)

26. Yuill, W., Edwards, A., Chowdhury, S., Chowdhury, S.P.: Optimal pmu placement: A comprehensive literature review. In: 2011 IEEE Power and Energy Society General Meeting. pp. 1-8 (July 2011)