Pith. sign in

REVIEW 1 major objections 5 minor 25 references

Failed power domination on graphs

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that deciding whether a graph has a failed power dominating set of size at least $k$ is NP-complete, and gives the first structural results for the failed power domination number.

desk verdict The failed power domination parameter is natural and the extremal results mostly hold up, but Section 3 proves NP-hardness for proper stalled subsets, not for arbitrary failed sets, and the transfer is not a formality. read the letter →

arxiv 1909.02057 v1 pith:KFCCXS2A submitted 2019-09-04 math.CO

Abraham Glasser , Bonnie Jacob , Emily Lederman , Stanis{l}aw Radziszowski This is my paper · ORCID
classification math.CO MSC 05C6905C8568Q17
keywords failedpowerdominationNP-completenessstalledsetnumberzeroforcinggraphproductsphasormeasurementunits
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces the failed power domination number $\bar\gamma_p(G)$, the largest number of vertices one can choose in a graph while failing to monitor the whole graph under the power-domination process used to model phasor-measurement placement in power grids; a set that succeeds in monitoring everything is a power dominating set (PDS). Its main result is that deciding whether $\bar\gamma_p(G) \ge k$ is NP-hard, so no efficient algorithm can compute this worst-case number for all graphs unless $\mathrm{P} \ne \mathrm{NP}$. The proof works by reducing the independent-set problem to the existence of large stalled sets, sets whose monitoring stops immediately after the initial domination step. The paper also characterizes the three largest possible failure values, gives sufficient conditions for the extreme value $\bar\gamma_p(G) = 0$, and computes exact values for complete bipartite graphs, ladder graphs, and $K_k \square P_\ell$.

What carries the argument

The load-bearing object is the stalled power dominating set (SPDS): a set $S$ satisfying $P^\infty(S) = P^0(S) = N[S]$, so that after the domination step the monitored set is already terminal. The reduction gadget for NP-hardness replaces each edge $e$ of the input graph $G$ with a subdivided path $P(e)$ of $n^2$ edges, adds a new vertex $x$ adjacent to all first subdivision vertices, and relies on Lemma 3.1 to force large stalled sets to touch each path heavily. Counting then shows any stalled set of size at least $n^2|E| + k$ consists of the path vertices plus an independent set of the original graph of size $k$, so the INDEPENDENT SET instance is encoded exactly. The same SPDS notion underlies the structural theorems, where the absence of propagation is what lets a set of $n-3$ vertices fail while almost all of the graph is monitored.

What would settle it

Run an exhaustive search over all graphs with at most seven vertices: for each subset, check whether it is failed, whether it is an inclusion-maximal failed set (no larger set containing it is also failed), and whether it is stalled (no propagation ever occurs). If some inclusion-maximal failed set is not stalled, the reduction's bridge from the stalled-subset decision problem to $\bar\gamma_p(G)$ fails; if none exists, the implicit lemma survives this test on small graphs.

Watch

Extended reading notes

Core claim

The central claim is that $\bar\gamma_p(G)$ is NP-hard to compute. The paper proves this by showing the decision problem FAILED POWER DOMINATING SET — does $G$ have a properly stalled subset of cardinality at least $m$? — is NP-complete, via a polynomial reduction from INDEPENDENT SET in which each edge of the input graph is replaced by a long subdivided path and a new vertex is attached to the subdivision vertices. A stalled set is one for which no propagation step occurs after domination, and the paper's treatment regards such sets as representing general failed sets at maximal size. On the structural side, the paper proves that $\bar\gamma_p(G) = n-1$ exactly when $G$ has an isolated vertex, $\bar\gamma_p(G) = n-2$ exactly when $G$ has a $K_2$ component and no isolated vertices, and $\bar\gamma_p(G) = n-3$ exactly when a specific induced $P_3$ or $K_3$ configuration is present. It further lists graph families with $\bar\gamma_p = 0$, shows that a graph with this property and a leaf or cut-vertex must be a path, and gives exact formulas for $K_{m,n}$, $P_k \square P_2$, and $K_k \square P_\ell$.

Load-bearing premise

The load-bearing assumption is the unstated claim that any failed set can be enlarged to a maximal failed set, and every maximal failed set is stalled; if that claim failed, the hardness proof would only cover sets that stop propagating immediately.

Editorial extensions

If this is right

  • If $\mathrm{P} \ne \mathrm{NP}$, no polynomial-time algorithm can compute $\bar\gamma_p(G)$ exactly on arbitrary graphs, so worst-case failed monitoring can never be certified efficiently in general.
  • Since any set of more than $\bar\gamma_p(G)$ vertices is a power dominating set, the number $\bar\gamma_p(G)+1$ is the smallest monitor count that guarantees full observation no matter where the monitors are placed; NP-hardness of $\bar\gamma_p$ makes that guaranteed count hard to determine as well.
  • The classifications of values $n-1$, $n-2$, and $n-3$ give a complete description of the three largest possible failure sizes in terms of components and small induced subgraphs.
  • If $\bar\gamma_p(G) = 0$, every nonempty set of vertices is a power dominating set; the paper's results imply that any such graph that is not a path is 2-connected.
  • Closed-form values for complete bipartite graphs, ladders, and $K_k \square P_\ell$ allow the exact worst-case failure size to be read off for these structured network families.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Supplying the missing maximality lemma would complete the reduction: if $w$ is the first vertex forced at step 1 by $v \notin S$, then $P^0(S \cup \{v\}) = P^1(S)$, so a maximal failed set cannot propagate; with this lemma, the NP-completeness of the stalled-subset problem becomes NP-hardness of $\bar\gamma_p(G)$ itself.
  • On the reduction gadget the same counting actually gives the exact identity $\bar\gamma_p(G') = n^2|E| + \alpha(G)$, so the construction is an exact gadget for the independence number, not just a one-way reduction.
  • A full characterization of $\bar\gamma_p = 0$ graphs is left open; Theorem 4.8 constrains the unknown cases to be 2-connected, so searching for minimal 2-connected graphs in which every single vertex is a PDS, beyond the chorded cycles of Theorem 4.6, is a natural next step.
  • Because $\bar\gamma_p(G) \le F(G)$, exact values for product graphs give lower bounds on failed zero forcing numbers, and any improved upper bound on failed zero forcing would transfer to an upper bound on $\bar\gamma_p$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper introduces the failed power domination number 𝛾̄p(G), the largest cardinality of a set that is not a power dominating set (PDS). It claims that computing 𝛾̄p(G) is NP-hard, characterizes graphs with 𝛾̄p(G) ≥ n−3, studies graphs with 𝛾̄p(G)=0, and computes 𝛾̄p for complete bipartite graphs and certain Cartesian products. The complexity proof reduces INDEPENDENT SET to a decision problem about the existence of a proper stalled subset of size at least m, using a construction that subdivides edges and attaches paths to each subdivision vertex.

Significance. If the NP-hardness claim were established, it would be the main contribution and would settle the computational complexity of a natural graph parameter related to power domination. The paper also contains structural results—characterizations of graphs with high 𝛾̄p, a partial list of graphs with 𝛾̄p=0, and exact values for special families—that are of independent interest. The zero-forcing connections and the poster list from [24] are useful. However, the central complexity claim is currently unsupported because the proof addresses a different decision problem than the one stated in the abstract.

major comments (1)
  1. [Section 3, first paragraph] The sentence 'In this section, we show that it is NP-hard to determine whether G has a failed power dominating set of cardinality at least k' is immediately followed by a formal problem definition that asks for a proper stalled subset. This is an inconsistency within Section 3 itself, independent of the abstract. The problem statement should match the claimed complexity result.
minor comments (5)
  1. [Title page] The author name 'Stanis/suppress law Radziszowski1' appears corrupted; it should read 'Stanisław Radziszowski'.
  2. [Section 4.1, Theorem 4.6] Items 3 and 4 in Theorem 4.6 are hard to parse, especially the definitions of P1 and P2 and the conditions i≥3, i≥5, and i+k≤n−1. The notation 'P1' and 'P2' conflicts with the use of Pi(S) for monitored sets; renaming these paths would improve clarity.
  3. [Section 5, Theorem 5.3] The proof uses both 'l' and 'ℓ' for the number of vertices in the path factor, and the inequality 'l ≥ 5' appears with lowercase l; the notation should be unified.
  4. [Section 4, Observation 4.1] Observation 4.1 states that P0(S)\S is a zero forcing set of G[V\S]. This is plausible but not proved; a one-line justification would help, since the observation is used in Theorem 4.8.
  5. [Section 2, Observation 2.2] The inequality 𝛾̄p(G) ≤ F(G) is stated without proof. A brief explanation that every failed PDS is also a failed zero forcing set would make the observation self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is self-contained, and cited external facts are standard and not equivalent to the claimed results.

full rationale

The paper's central complexity reduction, Lemma 3.2, reduces INDEPENDENT SET directly to the existence of a maximal properly stalled subset of a constructed graph, using standard external facts such as the domination number of a path, polynomial-time PDS verification, and Shitov's reduction template for failed zero forcing. The problem statement in Section 3 explicitly defines FAILED POWER DOMINATING SET as the proper-stalled-subset decision problem, so the NP-completeness proof is internally tied to that stated problem. Any mismatch between that formal decision problem and the informal phrase 'failed power dominating set' would be a proof gap, not a circular reduction: nothing in the proof assumes the conclusion it is trying to establish. The extreme-value characterizations in Sections 4 and 5 are proved directly from the definitions of PDS and FPDS, with no fitted parameters. The list attributed to a poster [24] is included and independently proved in Theorem 4.4. Citations to earlier power domination and zero forcing work are used for context, standard definitions, and known complexity tools, not as load-bearing self-citations that substitute for the argument. No parameter is fitted and then renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work to force a choice. Therefore no circular step can be exhibited, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numerical constants are fitted and no new physical or formal entities are postulated. The only implicit load-bearing assumption is the maximal-failed-sets-are-stalled transfer lemma, listed as an axiom.

assumptions (4)
  • standard math The domination number of a path on k vertices is ceil(k/3)
    Used in Lemma 3.1 to lower-bound how many vertices of each subdivided path a stalled set must contain.
  • standard math Path cover number is at most zero forcing number (Hogben, Theorem 2.13 in [18])
    Used in the degree-one case of Theorem 4.8 to conclude G-v is a path from Z(G-v)=1.
  • standard math Whether a set is a PDS can be verified in polynomial time ([16])
    Used in Theorem 3.3 to put FPDS in NP.
  • ad hoc to paper Every failed power dominating set can be extended to a maximal failed set, and maximal failed sets are stalled
    Implicitly required to move from NP-hardness for proper stalled subsets (the problem solved in Lemma 3.2) to NP-hardness of computing the maximum size of an arbitrary failed set (the abstract's claim). The lemma is true but is not stated or proved in the text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Failed power domination on graphs." pith.science (2026). https://pith.science/paper/KFCCXS2A

@misc{pith2026190902057,
  author       = {Pith},
  title        = {Pith review of: Failed power domination on graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KFCCXS2A}},
  note         = {Machine review of arXiv:1909.02057}
}
abstract

Let $G$ be a simple graph with vertex set $V$ and edge set $E$, and let $S \subseteq V$. The \emph{open neighborhood} of $v \in V$, $N(v)$, is the set of vertices adjacent to $v$; the \emph{closed neighborhood} is given by $N[v] = N(v) \cup \{v\}$. The \emph{open neighborhood} of $S$, $N(S)$, is the union of the open neighborhoods of vertices in $S$, and the \emph{closed neighborhood} of $S$ is $N[S] = S \cup N(S)$. The sets $ \mathcal{P}^i(S), i \geq 0$, of vertices \emph{monitored} by $S$ at the $i^{\ {th}}$ step are given by $\mathcal{P}^0(S) = N[S]$ and $\mathcal{P}^{i+1}(S) = \mathcal{P}^i(S) \bigcup\left\{ w : \{ w \} = N[v] \backslash \mathcal{P}^i(S) \ { for some } v \in \mathcal{P}^i(S) \right\}$. If there exists $j$ such that $\mathcal{P}^j(S) = V$, then $S$ is called a \emph{power dominating set}, PDS, of $G$. We introduce and discuss the \emph{failed power domination number} of a graph $G$, $\bar{\gamma}_p(G)$, the largest cardinality of a set that is not a PDS. We prove that $\bar{\gamma}_p(G)$ is NP-hard to compute, determine graphs in which every vertex is a PDS, and compare $\bar{\gamma}_p(G)$ to similar parameters.

Figures

Figures reproduced from arXiv: 1909.02057 by the authors.

Figure 1
Figure 1. A PDS S in blue 05 04 03 02 01 00 15 14 13 12 11 10 25 24 23 22 21 20 35 34 33 32 31 30 45 44 43 42 41 40 55 54 53 52 51 50 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. A graph G with in￾dependent set of cardinality 2 shown in blue ve0 ve1 ve2 e1 ve15 ve16 e2 e16 vf0 vf1 vf2 vf15 vf16 f1 f2 f16 vg0 vg1 vg2 vg15 vg16 g1 g2 g16 vh0 vh1 vh2 h1 vh15 vh16 h2 h16 x [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. The graph G′ with FPDS S in blue, |S| = 66 3. For each e = {u, v} ∈ E, add vertices ve1 through ven2 to V ′ . For each i = 1, 2, . . . , n2 , let V ′ i denote all vi ∈ V ′ , and add edge ei = {vei−1 , vei } to E′ . Let P(e) denote the path from ve0 to ven2 . Let the set of all such paths be denoted ρ. 4. Add a vertex x to V ′ . For each vertex ve0 ∈ V ′ 0 , add {x, ve0 } to E′ . To see that U ′ is an SPDS in G′ , no… view at source ↗
Figures from the paper (2 more)
Figure 5
Figure 5. Figure 5: A graph G with ¯γp(G) = 0 as in Theorem 4.6, item 4. S = {v3} is shown in blue on the left, followed by P 0 (S) through P 3 (S). Continuing, P 4 (S) = {v1, v2, . . . v8}, and P 5 (S) = V . Proof. For each j ≥ 0, Qj (S ′ ) ⊆ Pi+j (S). Thus, if Q∞(S ′ ) = V , then P∞(S ′…
Figure 6
Figure 6. Figure 6: A ladder graph, P9P2 with FPDS S in blue on the left and P 0 (S) in blue on the right. For graphs G and H, we denote by GH the Cartesian product of G and H, where V (GH) = V (G) × V (H). If u1, u2 ∈ V (G) and v1, v2 ∈ V (H), then (u1, v1) is adjacent to (u2, v2) in GH …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [24]

    Failed power domination

    Jonathan Tostado-Marquez. Failed power domination. I n Society for Advancement of Chi- canos/Hispanics and Native Americans in Science (SACNAS) Na tional Diversity in STEM Conference, October 2017

    work page 2017

  2. [1]

    Domination in graphs with bounded propag ation: algorithms, formulations and hardness results

    Ashkan Aazami. Domination in graphs with bounded propag ation: algorithms, formulations and hardness results. Journal of Combinatorial Optimization , 19(4):429–456, 2010

    work page 2010

  3. [2]

    Zero forcin g sets and the minimum rank of graphs

    AIM Minimum Rank-Special Graphs Work Group. Zero forcin g sets and the minimum rank of graphs. Linear Algebra and its Applications , 428(7):1628–1648, 2008

    work page 2008

  4. [3]

    Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns , Palo Alto, CA, October 2006

    American Institute of Mathematics Workshop. Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns , Palo Alto, CA, October 2006. Webpage: http://aimath.org/pastworkshops/matrixspectrum.html

    work page 2006

  5. [4]

    Failed skew zero forcing on a graph

    Thomas Ansill, Bonnie Jacob, Jaime Penzellna, and Danie l Saavedra. Failed skew zero forcing on a graph. Linear Algebra and its Applications , 509:40–63, 2016

    work page 2016

  6. [5]

    Baldwin, L

    T.L. Baldwin, L. Mili, M.B. Boisen, and R. Adapa. Power sy stem observability with minimal phasor measurement placement. IEEE Transactions on Power Systems , 8(2):707–715, 1993

    work page 1993

  7. [6]

    Fallat, H

    Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tr acy Hall, Leslie Hogben, Bryan Shader, P. Van Den Driessche, and Hein Van Der Holst. Zero for cing parameters and minimum rank problems. Linear Algebra and its Applications , 433(2):401–411, 2010. 11

    work page 2010

  8. [7]

    Fallat, H

    Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tr acy Hall, Leslie Hogben, and Hein van der Holst. On the graph complement conjecture for minimu m rank. Linear Algebra and its Applications, 436(12):4373–4391, 2012

    work page 2012

Show all 25 references
  1. [8]

    Benson, Daniela Ferrero, Mary Flagg, Veron ika Furst, Leslie Hogben, Violeta Vasilevska, and Brian Wissman

    Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veron ika Furst, Leslie Hogben, Violeta Vasilevska, and Brian Wissman. Zero forcing and power domin ation for graph products. The Australasian Journal of Combinatorics , 70:221–235, 2018

    2018

  2. [9]

    Local controlla- bility of quantum networks

    Daniel Burgarth, Sougato Bose, Christoph Bruder, and Vi ttorio Giovannetti. Local controlla- bility of quantum networks. Physical Review A , 79(6):060305, 2009

    2009

  3. [10]

    Zero forcing, linear and quantum controllability fo r systems evolving on networks

    Daniel Burgarth, Domenico D’Alessandro, Leslie Hogbe n, Simone Severini, and Michelle Young. Zero forcing, linear and quantum controllability fo r systems evolving on networks. IEEE Transactions on Automatic Control , 58(9):2349–2354, 2013

    2013

  4. [11]

    Full contro l by locally induced relaxation

    Daniel Burgarth and Vittorio Giovannetti. Full contro l by locally induced relaxation. Physical Review Letters, 99(10):100501, 2007

    2007

  5. [12]

    Indirect Hamiltoni an identification through a small gateway

    Daniel Burgarth and Koji Maruyama. Indirect Hamiltoni an identification through a small gateway. New Journal of Physics , 11(10):103019, 2009

    2009

  6. [13]

    Daniela Ferrero, Leslie Hogben, Franklin H. J. Kenter, and Michael Young. Note on power propagation time and lower bounds for the power domination n umber. Journal of Combina- torial Optimization , 34(3):736–741, 2017

    2017

  7. [14]

    T he failed zero forcing number of a graph

    Katherine Fetcie, Bonnie Jacob, and Daniel Saavedra. T he failed zero forcing number of a graph. Involve, pages 99–117, 2015

    2015

  8. [15]

    Henning, Bert Randerath, an d Preben Dahl Vestergaard

    Allan Frendrup, Michael A. Henning, Bert Randerath, an d Preben Dahl Vestergaard. An upper bound on the domination number of a graph with minimum degree 2. Discrete Mathematics , 309(4):639–646, 2009

    2009

  9. [16]

    Haynes, Sandra M

    Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hede tniemi, and Michael A. Henning. Domination in graphs applied to electric power networks. SIAM Journal on Discrete Mathe- matics, 15(4):519–529, 2002

    2002

  10. [17]

    Heydt, Chen-Ching Liu, A.G

    G.T. Heydt, Chen-Ching Liu, A.G. Phadke, and Vijay Vitt al. Solution for the crisis in electric power supply. IEEE Computer applications in Power , 14(3):22–30, 2001

    2001

  11. [18]

    Minimum rank problems

    Leslie Hogben. Minimum rank problems. Linear Algebra and its Applications , 432(8):1961– 1974, 2010

    1961

  12. [19]

    Parameterized power domination complexity

    Joachim Kneis, Daniel M¨ olle, Stefan Richter, and Pete r Rossmanith. Parameterized power domination complexity. Information Processing Letters , 98(4):145–149, 2006

    2006

  13. [20]

    Nuqui and Arun G

    Reynaldo F. Nuqui and Arun G. Phadke. Phasor measuremen t unit placement techniques for complete and incomplete observability. IEEE Transactions on Power Delivery , 20(4):2381– 2388, 2005

    2005

  14. [21]

    Darren D. Row. A technique for computing the zero forcin g number of a graph with a cut- vertex. Linear Algebra and its Applications , 436(12):4423–4432, 2012

    2012

  15. [22]

    Nondiscriminatory propagation on tr ees

    Simone Severini. Nondiscriminatory propagation on tr ees. Journal of Physics A: Mathematical and Theoretical, 41(48):482002, 2008. 12

    2008

  16. [23]

    On the complexity of failed zero forci ng

    Yaroslav Shitov. On the complexity of failed zero forci ng. Theoretical Computer Science , 660:102–104, 2017

    2017

  17. [25]

    Vijayakumar, and Andreas M

    Seethu Varghese, A. Vijayakumar, and Andreas M. Hinz. P ower domination in Kn¨ odel graphs and Hanoi graphs. Discussiones Mathematicae Graph Theory , 38(1):63–74, 2018. 13

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.