{"id":"866940af-ff46-4ef4-bbe6-c3c63ed837c1","arxiv_id":"1909.02057","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The failed power domination number is NP-hard to compute, and exact values are given for complete bipartite graphs, ladders, and layered complete graphs.","lead":"This paper introduces the failed power domination number, the largest number of monitoring devices that can be placed on a power network without observing the whole network. It proves this number is NP-hard to compute and gives exact values for several graph families, which matters for worst-case sensor placement.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3 is proved for proper stalled subsets only; the transfer to arbitrary failed sets is unproved, and the natural transfer lemma is false, so the abstract's NP-hardness claim is not currently supported.","rationale":"The reader's weakest assumption identifies the same gap: the reduction solves a proper-stalled-subset problem while the abstract claims hardness for maximum arbitrary failed sets. However, the reader's proposed repair is incorrect: every maximal failed set is not stalled, as shown by the 6-vertex counterexample. This makes the concern more serious, because the missing transfer cannot be filled by the stated lemma. The reduction itself may still be repairable by proving that in the constructed graph G' the maximum failed set has the same value as the maximum stalled set, or by building a different reduction for failed sets, but that argument is absent. The proofs in Sections 4 and 5 have additional unhandled cases, but those do not affect the NP-hardness claim as directly. Since the main abstract claim is currently unsupported but plausibly repairable, the appropriate verdict is CONDITIONAL rather than REJECT or UNCHANGED.","tokens_in":13934,"tokens_out":21810,"duration_ms":236077,"concrete_test":"Enumerate all subsets of the 6-vertex graph with edges ac, bc, cy, yz1, yz2 and verify that S = {a,b} has P∞(S) = {a,b,c,y} while S∪{y}, S∪{z1}, and S∪{z2} are each PDS; this falsifies the transfer lemma 'maximal failed implies stalled'. Then, to test the paper's reduction directly, for a small source graph G (e.g., G = P3), construct G' as in Lemma 3.2, exhaustively compute M_failed = max{|S| : P∞(S) ≠ V(G')} and M_stalled = max{|S| : P1(S) = P0(S) ≠ V(G')}, and compare. If M_failed > M_stalled, the reduction as written cannot establish NP-hardness of ¯γp(G).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The decision problem stated in Section 3 is: 'Does G have a proper stalled subset of cardinality at least m?' The abstract and Theorem 3.3 instead claim NP-hardness of computing ¯γp(G), the maximum size of an arbitrary failed PDS. Nothing in the paper proves that these decision problems are equivalent, and the transfer is not a formality: a failed set need not be stalled. The reader's proposed bridge ('every maximal failed set is stalled') is false. In the graph with edges ac, bc, cy, yz1, yz2, take S = {a, b}. Then P0(S) = {a,b,c}, P1(S) = {a,b,c,y}, and P∞(S) = {a,b,c,y} ≠ V, so S is failed but not stalled. Adding y, z1, or z2 to S each produces a PDS, so S is inclusion-maximal among failed sets. Thus maximality among failed sets does not imply stalled. Lemma 3.1 and the converse half of Lemma 3.2 are stated for SPDS or 'maximally stalled' sets, so as written Theorem 3.3 establishes only NP-completeness of the proper-stalled-subset problem. The central claim therefore has a real gap; it needs a different argument relating large failed sets to the constructed graph, not the asserted-maximality lemma.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14201,"tokens_out":3857,"duration_ms":39691,"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":[{"comment":"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.","section":"Section 3, first paragraph"}],"minor_comments":[{"comment":"The author name 'Stanis/suppress law Radziszowski1' appears corrupted; it should read 'Stanisław Radziszowski'.","section":"Title page"},{"comment":"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.","section":"Section 4.1, Theorem 4.6"},{"comment":"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.","section":"Section 5, Theorem 5.3"},{"comment":"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.","section":"Section 4, Observation 4.1"},{"comment":"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.","section":"Section 2, Observation 2.2"}],"recommendation":"reject","confidential_remarks":"The central NP-hardness claim is not supported by the proof, and the natural bridging lemma is false, so the paper's main contribution collapses. The structural results in Sections 4 and 5 may be salvageable as a separate paper, but as submitted the manuscript does not meet the bar for publication. I would suggest the authors either find a genuinely different reduction for 𝛾̄p(G) or reframe the paper around the complexity of the proper-stalled-subset problem, which is a different parameter."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper introduces a sensible new parameter, gives a clean extremal characterization for n−3, and provides some nice product formulas. But the main theorem, that computing the failed power domination number is NP-hard, is not proven as written.\n\nSection 3 defines FAILED POWER DOMINATING SET as the existence of a proper stalled subset of size at least m, then Theorem 3.3 claims NP-completeness for ordinary failed power dominating sets. The proof never connects the two problems. The reader's initial guess was that every maximal failed set is stalled; that is false. In the graph with edges ac, bc, cy, yz1, yz2, take S={a,b}. Then P0={a,b,c}, P1={a,b,c,y}, and P∞=P1≠V, so S is failed but not stalled. Adding y, z1, or z2 each makes a PDS, so S is maximal among failed sets yet not stalled. Thus the reduction only establishes hardness for the proper-stalled-subset decision problem, and the abstract's claim about computing γ̄p(G) is unsupported. Maybe the constructed graph has extra properties that let you transfer, but the paper doesn't show that.\n\nWhat is genuinely new: the parameter itself, the n−3 characterization, the join lemma, and the explicit formulas for Km,n, Pk□P2, and Kk□Pℓ. The authors credit Tostado's poster for the list of graphs with γ̄p=0 and supply proofs, which is good practice. The reduction from Independent Set is structurally sound for proper stalled subsets, and that part has real content.\n\nOther soft spots are minor: a few upper-bound proofs in Section 5 leave case checks to the reader, and the cut-vertex argument in Theorem 4.8 is a bit terse. These look repairable. The core gap is the missing transfer from stalled to arbitrary failed sets, and it is load-bearing.\n\nWho is this for? Researchers working on power domination or failed variants of zero forcing. The paper deserves a serious referee, but the referee should focus on whether the reduction can be adapted to ordinary failed sets or whether the theorem statement must be weakened. I would not cite the NP-hardness result in its current form.","headline":"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.","tokens_in":14741,"tokens_out":3656,"would_cite":false,"duration_ms":38608,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["failed power domination","power domination","NP-completeness","stalled set","domination number","zero forcing","graph products","phasor measurement units"],"falsifier":"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.","tokens_in":13722,"feed_emoji":"⚡","tokens_out":13498,"duration_ms":130256,"temperature":0.7,"pith_summary":"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$.","feed_headline":"Biggest failing sensor sets are NP-hard to find","feed_subtitle":"New graph number captures worst-case power-grid monitoring; hardness follows from independent set.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the failed-zero-forcing NP-completeness technique and the connected INDEPENDENT SET reduction that Lemma 3.2 adapts.","marker":"[23]"},{"why":"Formulates power domination as a graph problem and provides the polynomial-time verification that a set is a PDS used to place FPDS in NP.","marker":"[16]"},{"why":"Formalizes the monitored-set iteration $P^i(S)$ adopted in the paper's definitions.","marker":"[1]"},{"why":"Supplies the electric power network observability problem and PMU placement motivation that defines the parameter's applied meaning.","marker":"[5]"},{"why":"Gives the domination number of a path, used in Lemma 3.1 to constrain stalled sets inside pendant paths.","marker":"[15]"},{"why":"Supplies the path-cover bound used in Theorem 4.8 to force $\\bar\\gamma_p = 0$ graphs with a leaf or cut-vertex to be paths.","marker":"[18]"},{"why":"Is the poster source for the listed families with $\\bar\\gamma_p = 0$ reproduced in Theorem 4.4.","marker":"[24]"}],"fun_headline_variants":["Largest failed sensor set is NP-hard to find","NP-hardness of maximal power-domination failures","Counting failed domination sets? NP-hard","Maximal power-domination failure count is NP-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Largest failed sensor set is NP-hard to find","NP-hardness of maximal power-domination failures","Counting failed domination sets? NP-hard","Maximal power-domination failure count is NP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000434,"raw_usage":{"total_tokens":2315,"prompt_tokens":1151,"completion_tokens":1164,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":767,"completion_tokens_details":{"reasoning_tokens":1105}},"tokens_in":767,"tokens_out":1164,"duration_ms":10251,"temperature":1.0,"reasoning_tokens":1105,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:07:18.277693+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On the complexity of failed zero forci ng","cited_arxiv_id":null,"evidence_quote":"Supplies the failed-zero-forcing NP-completeness technique and the connected INDEPENDENT SET reduction that Lemma 3.2 adapts."},{"cited_title":"Haynes, Sandra M","cited_arxiv_id":null,"evidence_quote":"Formulates power domination as a graph problem and provides the polynomial-time verification that a set is a PDS used to place FPDS in NP."},{"cited_title":"Domination in graphs with bounded propag ation: algorithms, formulations and hardness results","cited_arxiv_id":null,"evidence_quote":"Formalizes the monitored-set iteration $P^i(S)$ adopted in the paper's definitions."},{"cited_title":"Baldwin, L","cited_arxiv_id":null,"evidence_quote":"Supplies the electric power network observability problem and PMU placement motivation that defines the parameter's applied meaning."},{"cited_title":"Henning, Bert Randerath, an d Preben Dahl Vestergaard","cited_arxiv_id":null,"evidence_quote":"Gives the domination number of a path, used in Lemma 3.1 to constrain stalled sets inside pendant paths."},{"cited_title":"Minimum rank problems","cited_arxiv_id":null,"evidence_quote":"Supplies the path-cover bound used in Theorem 4.8 to force $\\bar\\gamma_p = 0$ graphs with a leaf or cut-vertex to be paths."},{"cited_title":"Failed power domination","cited_arxiv_id":null,"evidence_quote":"Is the poster source for the listed families with $\\bar\\gamma_p = 0$ reproduced in Theorem 4.4."}],"review_version":1}