pith. sign in

arxiv: 2605.18533 · v1 · pith:M3KS444Cnew · submitted 2026-05-18 · 🧮 math.OC · cs.DM

Capacitated power dominating set problem: a solution approach based on forbidden propagation sets

Mauro Lucci , Diego Delle Donne , Mariana Escalante This is my paper

Pith reviewed 2026-05-20 08:40 UTC · model grok-4.3

classification 🧮 math.OC cs.DM
keywords capacitated power dominating setforbidden propagation setsinteger linear programminglazy constraint separationpower system monitoringcombinatorial optimizationnetwork placement problems
0
0 comments X

The pith

Forbidden propagation sets enable new integer programs for capacitated power dominating sets that avoid big-M constraints and run faster on large networks.

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

The paper establishes that forbidden propagation sets, structures that cannot appear together in any valid placement of measurement devices, allow integer linear programs for the capacitated power dominating set problem without relying on big-M constraints. These formulations use infection-based variables and an exponential number of constraints separated lazily through cycle detection. A sympathetic reader would care because real power systems have capacity limits on devices, and solving the placement problem efficiently matters for monitoring large networks up to fourteen thousand vertices. The results show an average one point seven times speedup over adapted existing methods, with performance also depending on the specific capacity values.

Core claim

The paper claims that introducing forbidden propagation sets as novel combinatorial structures enables a new class of integer linear programming formulations for the capacitated power dominating set problem. These formulations combine infection-based variables with exponentially many constraints while avoiding big-M constraints, supported by derived structural properties, valid inequalities, and redundancy-breaking constraints. An efficient lazy-separation procedure based on cycle detection is designed, and computational experiments demonstrate an average execution-time improvement of 1.7 times over existing approaches on benchmark instances with up to 14,000 vertices.

What carries the argument

Forbidden propagation sets are combinatorial structures that cannot occur simultaneously in any feasible solution. They carry the argument by enabling ILP formulations that use infection-based variables with exponentially many constraints separated on the fly, avoiding big-M terms.

If this is right

  • The formulations achieve an average 1.7x execution time improvement on instances up to 14,000 vertices.
  • Performance depends on both network size and the capacities assigned to the devices.
  • Structural properties, valid inequalities, and redundancy-breaking constraints can be derived from the forbidden propagation sets.
  • The lazy separation procedure based on cycle detection handles the exponential constraints efficiently in practice.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar forbidden-set constructions could apply to other capacitated network monitoring or domination problems beyond power systems.
  • Testing the method on real power grid topologies with heterogeneous capacities would reveal whether the observed speedups hold outside synthetic benchmarks.
  • The approach might integrate with decomposition techniques to scale further on instances exceeding 14,000 vertices.

Load-bearing premise

The load-bearing premise is that the lazy-separation procedure based on cycle detection can efficiently identify all relevant forbidden propagation sets without excessive overhead or missing critical constraints that affect solution quality.

What would settle it

Running the new formulations on the same benchmark instances with up to 14,000 vertices and finding no average execution-time improvement or worse solution quality than adapted existing methods would falsify the performance claim.

Figures

Figures reproduced from arXiv: 2605.18533 by Diego Delle Donne, Mariana Escalante, Mauro Lucci.

Figure 1
Figure 1. Figure 1: Example of the step-by-step calculation of the monitored set. Colors indicate the rule applied: [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two pairs of propagation sets (in cyan) and their corresponding precedence digraphs. The leftmost [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Two pairs of FPSs (in cyan) and their precedence digraphs: (a) an FPS that minimally imposes [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Two pairs of propagation sets (in cyan) and their corresponding precedence digraphs, where each [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) The cyan FPS imposes the magenta chordless cycle in the precedence digraph; (b) the dashed [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The cyan propagations are FPSs that minimally impose 2-cycles. [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Results of the comparison between FPS-IP and EFPS-IP [PITH_FULL_IMAGE:figures/full_fig_p021_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Evolution of the execution time for EFPS-IP and EFPS-IP with respect to capacity for selected [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Results of the experiment with model tightening and initial constraints [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Comparison between EFPS-IP and existing models from the literature [PITH_FULL_IMAGE:figures/full_fig_p024_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Evolution of the execution time for EFPS-IP-OutP-Init and existing models from the literature [PITH_FULL_IMAGE:figures/full_fig_p025_11.png] view at source ↗
read the original abstract

The optimal placement of measurement devices in electrical power systems is commonly modeled through the power dominating set problem. However, in real-world applications, these devices have limited capacities, leading to a capacitated variant of the problem that has received little attention in the literature. In this work, we introduce forbidden propagation sets, novel combinatorial structures that cannot occur simultaneously in any feasible solution. This notion enables a new class of integer linear programming formulations. They combine infection-based variables with exponentially many constraints, while avoiding big-$M$ constraints. We derive structural properties, valid inequalities, and redundancy-breaking constraints, and design an efficient lazy-separation procedure based on cycle detection. Computational experiments on benchmark instances with up to 14,000 vertices show that the proposed method achieves an average execution-time improvement of 1.7x over existing approaches adapted from the literature. Moreover, the results indicate that performance depends not only on network size, but also on capacities.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript addresses the capacitated power dominating set (CPDS) problem, which models optimal placement of limited-capacity measurement devices in power systems. It introduces forbidden propagation sets as novel combinatorial structures that cannot occur in feasible solutions. These enable new ILP formulations combining infection variables with exponentially many constraints that avoid big-M terms. The authors derive structural properties, valid inequalities, and redundancy-breaking constraints, and propose a lazy-separation procedure based on cycle detection. Computational experiments on benchmark instances with up to 14,000 vertices report an average 1.7x execution-time improvement over adapted literature approaches, with performance also depending on network capacities.

Significance. If the formulations are valid and the separation procedure is complete, the work provides a meaningful advance for solving large-scale CPDS instances without relying on big-M constraints. The introduction of forbidden propagation sets offers a clean combinatorial perspective that strengthens the theoretical foundation. The reported results on instances with 14,000 vertices are practically relevant for power-system applications, and the observation that performance depends on capacities adds nuance beyond size alone. The paper does not include machine-checked proofs or open reproducible code, but the benchmark comparison on standard instances is a positive element.

major comments (2)
  1. [§4.2] §4.2 (Lazy-separation procedure): The description states that the procedure relies on cycle detection to identify violated forbidden-propagation-set inequalities. However, no argument or proof is given that every forbidden propagation set corresponds to a detectable cycle or that the procedure adds all violated cuts before the solver terminates. Without this completeness guarantee, the relaxation solved may be incomplete, which directly affects the claimed optimality of solutions and the validity of the 1.7x runtime comparison to literature baselines.
  2. [§5] §5 (Computational experiments): The reported average 1.7x improvement is presented as evidence of superiority, yet the experimental section does not include an ablation or verification step confirming that all relevant forbidden-set cuts were added in the solved instances. If any critical cuts were missed on the larger graphs, the timing results would reflect an incomplete model rather than a fair comparison.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'structural properties' is used without a forward reference to the specific section or theorem where they are stated; adding a pointer would improve readability.
  2. [§3] Notation: the definition of infection variables and their relation to propagation sets could be clarified with a small illustrative example early in §3 to help readers unfamiliar with power-domination terminology.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments on the capacitated power dominating set problem. We address the major comments point by point below and indicate the changes we will make to strengthen the presentation.

read point-by-point responses

  1. Referee: [§4.2] §4.2 (Lazy-separation procedure): The description states that the procedure relies on cycle detection to identify violated forbidden-propagation-set inequalities. However, no argument or proof is given that every forbidden propagation set corresponds to a detectable cycle or that the procedure adds all violated cuts before the solver terminates. Without this completeness guarantee, the relaxation solved may be incomplete, which directly affects the claimed optimality of solutions and the validity of the 1.7x runtime comparison to literature baselines.

    Authors: We acknowledge that Section 4.2 describes the cycle-detection mechanism but does not contain an explicit completeness argument. We will add a formal proof in the revised manuscript showing that a forbidden propagation set exists if and only if a cycle satisfying the capacity-derived conditions is present in the auxiliary propagation graph. The proof relies on the structural properties already derived in Section 3 and establishes that the separation routine identifies every minimal violated inequality. Consequently, the solver terminates only after all relevant cuts have been added, preserving optimality and the validity of the reported runtime comparisons. revision: yes

  2. Referee: [§5] §5 (Computational experiments): The reported average 1.7x improvement is presented as evidence of superiority, yet the experimental section does not include an ablation or verification step confirming that all relevant forbidden-set cuts were added in the solved instances. If any critical cuts were missed on the larger graphs, the timing results would reflect an incomplete model rather than a fair comparison.

    Authors: We agree that an explicit verification step would increase confidence in the experimental results. In the revised Section 5 we will include, for every solved instance, the total number of forbidden-propagation-set cuts separated during the run together with a post-optimization check confirming that the final integer solution induces no remaining cycles in the propagation graph. This will demonstrate that the model solved was complete and that the observed 1.7x average speedup is obtained under a fully separated formulation. revision: yes

Circularity Check

0 steps flagged

No circularity: formulations and separation derived from standard graph-theoretic definitions

full rationale

The paper introduces forbidden propagation sets as new combinatorial objects defined directly from the capacitated power domination rules, then builds ILP formulations using infection variables and exponential inequalities without big-M terms. The lazy separation is presented as a cycle-detection procedure grounded in the structural properties derived earlier in the manuscript. No load-bearing step reduces by construction to a fitted parameter, self-citation chain, or renamed input; the 1.7x runtime claim is an empirical outcome on external benchmark instances rather than a tautological prediction. The derivation remains self-contained against standard ILP and graph theory primitives.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The approach rests on the introduction of forbidden propagation sets as new entities and standard assumptions from integer programming and graph theory for deriving valid inequalities and separation routines.

axioms (1)
  • standard math Standard properties of integer linear programming formulations and valid inequalities apply to the derived constraints.
    Invoked to support structural properties and redundancy-breaking constraints.
invented entities (1)
  • forbidden propagation sets no independent evidence
    purpose: To generate exponentially many valid inequalities for capacitated power dominating set ILP models without requiring big-M terms.
    Newly defined combinatorial structures that cannot occur simultaneously in any feasible solution.

pith-pipeline@v0.9.0 · 5694 in / 1208 out tokens · 53758 ms · 2026-05-20T08:40:36.668400+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    and Mili, L

    Baldwin, T.L. and Mili, L. and Boisen, M.B. and Adapa, R. , journal=. Power system observability with minimal phasor measurement placement , year=

    work page

  2. [2]

    and Hedetniemi, Sandra M

    Haynes, Teresa W. and Hedetniemi, Sandra M. and Hedetniemi, Stephen T. and Henning, Michael A. , title =. SIAM Journal on Discrete Mathematics , volume =. 2002 , abstract =

    work page 2002

  3. [3]

    and Heath, Lenwood S

    Brueni, Dennis J. and Heath, Lenwood S. , title =. SIAM Journal on Discrete Mathematics , volume =. 2005 , abstract =

    work page 2005

  4. [4]

    Algorithmica , year=

    Guo, Jiong and Niedermeier, Rolf and Raible, Daniel , title=. Algorithmica , year=

    work page

  5. [5]

    Power domination in block graphs , journal =

    Guangjun Xu and Liying Kang and Erfang Shan and Min Zhao , keywords =. Power domination in block graphs , journal =. 2006 , issn =

    work page 2006

  6. [6]

    Henning , keywords =

    Michael Dorfling and Michael A. Henning , keywords =. A note on power domination in grid graphs , journal =. 2006 , issn =

    work page 2006

  7. [7]

    Power Domination Problem in Graphs

    Liao, Chung-Shou and Lee, Der-Tsai. Power Domination Problem in Graphs. Proceedings of the International Computing and Combinatorics Conference. 2005

    work page 2005

  8. [8]

    Liao, Chung-Shou and Lee, D. T. , title=. Algorithmica , year=

    work page

  9. [9]

    2020 , editor =

    Dorbec, Paul , booktitle =. 2020 , editor =

    work page 2020

  10. [10]

    Algorithmica , year=

    Binkele-Raible, Daniel and Fernau, Henning , title=. Algorithmica , year=

    work page

  11. [11]

    Journal of Combinatorial Optimization , year=

    Aazami, Ashkan , title=. Journal of Combinatorial Optimization , year=

    work page

  12. [12]

    Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming

    Fan, Neng and Watson, Jean-Paul. Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming. Proceedings of the International Conference on Combinatorial Optimization and Applications. 2012

    work page 2012

  13. [13]

    Energy Systems , year=

    Fan, Neng and Watson, Jean-Paul , title=. Energy Systems , year=

    work page

  14. [14]

    Journal of Combinatorial Optimization , year=

    Bozeman, Chassidy and Brimkov, Boris and Erickson, Craig and Ferrero, Daniela and Flagg, Mary and Hogben, Leslie , title=. Journal of Combinatorial Optimization , year=

    work page

  15. [15]

    Journal of Combinatorial Optimization , year=

    Brimkov, Boris and Mikesell, Derek and Smith, Logan , title=. Journal of Combinatorial Optimization , year=

    work page

  16. [16]

    Expert Systems , volume =

    Jovanovic, Raka and Voss, Stefan , title =. Expert Systems , volume =. 2020 , doi=

    work page 2020

  17. [17]

    and Hicks, Illya V

    Smith, Logan A. and Hicks, Illya V. , title =. Networks , volume =

    work page

  18. [18]

    An Efficient Algorithm for Power Dominating Set , year =

    Bl\". An Efficient Algorithm for Power Dominating Set , year =. Algorithmica , month = dec, pages =

    work page

  19. [19]

    Observability of power systems with optimal PMU placement , journal =

    Margarida Carvalho and Xenia Klimentova and Ana Viana , keywords =. Observability of power systems with optimal PMU placement , journal =. 2018 , issn =

    work page 2018

  20. [20]

    , journal=

    Gharani Khajeh, Kiarash and Bashar, Erfan and Mahboub Rad, Ali and Gharehpetian, Gevork B. , journal=. Integrated Model Considering Effects of Zero Injection Buses and Conventional Measurements on Optimal PMU Placement , year=

    work page

  21. [21]

    Generalized Integer Linear Programming Formulation for Optimal PMU Placement , year=

    Gou, Bei , journal=. Generalized Integer Linear Programming Formulation for Optimal PMU Placement , year=

    work page

  22. [22]

    Journal of Electrical Engineering

    Niyaragh, Seyed Mehdi Mirkazemi and Irani, Aref Jalili and Shayeghi, Hossein , title=. Journal of Electrical Engineering. 2020 , month=

    work page 2020

  23. [23]

    and Ismail, Hanafy Mahmoud , journal=

    Abbasy, Nabil H. and Ismail, Hanafy Mahmoud , journal=. A Unified Approach for the Optimal PMU Location for Power System State Estimation , year=

    work page

  24. [24]

    Enhanced Optimal PMU Placements With Limited Observability Propagations , year=

    Guo, Xian-Chang and Liao, Chung-Shou and Chu, Chia-Chi , journal=. Enhanced Optimal PMU Placements With Limited Observability Propagations , year=

    work page

  25. [25]

    Anderson and K

    S.E. Anderson and K. Kuenzel , keywords =. Power domination in cubic graphs and Cartesian products , journal =. 2022 , issn =

    work page 2022

  26. [26]

    Allan and Renu Laskar , abstract =

    Robert B. Allan and Renu Laskar , abstract =. On domination and independent domination numbers of a graph , journal =. 1978 , issn =

    work page 1978

  27. [27]

    Placement of PMUs with channel limits , year=

    Korkali, Mert and Abur, Ali , booktitle=. Placement of PMUs with channel limits , year=

    work page

  28. [28]

    2008 , issn =

    Zero forcing sets and the minimum rank of graphs , journal =. 2008 , issn =

    work page 2008

  29. [29]

    and Korres, George N

    Manousakis, Nikolaos M. and Korres, George N. and Georgilakis, Pavlos S. , journal=. Taxonomy of PMU Placement Methodologies , year=

    work page

  30. [30]

    Verma , keywords =

    Prachi Mafidar Joshi and H.K. Verma , keywords =. Synchrophasor measurement applications and optimal PMU placement: A review , journal =. 2021 , issn =

    work page 2021

  31. [31]

    A Fault-Tolerance Based Approach to Optimal PMU Placement , year=

    Almasabi, Saleh and Mitra, Joydeep , journal=. A Fault-Tolerance Based Approach to Optimal PMU Placement , year=

    work page

  32. [32]

    Real-Time Faulted Line Localization and PMU Placement in Power Systems Through Convolutional Neural Networks , year=

    Li, Wenting and Deka, Deepjyoti and Chertkov, Michael and Wang, Meng , journal=. Real-Time Faulted Line Localization and PMU Placement in Power Systems Through Convolutional Neural Networks , year=

    work page

  33. [33]

    Strategic placements of PMUs for power network observability considering redundancy measurement , journal =

    Rohit Babu and Biplab Bhattacharyya , keywords =. Strategic placements of PMUs for power network observability considering redundancy measurement , journal =. 2019 , issn =

    work page 2019

  34. [34]

    Multistage Optimal PMU Placement Considering Substation Infrastructure , year=

    Almasabi, Saleh and Mitra, Joydeep , journal=. Multistage Optimal PMU Placement Considering Substation Infrastructure , year=

    work page

  35. [35]

    and Abur, A

    Xu, B. and Abur, A. , booktitle=. Observability analysis and measurement placement for systems with PMUs , year=

    work page

  36. [36]

    Dua, Devesh and Dambhare, Sanjay and Gajbhiye, Rajeev Kumar and Soman, S. A. , journal=. Optimal Multistage Scheduling of PMU Placement: An ILP Approach , year=

    work page

  37. [37]

    Synchrophasor Measurement Technology in Power Systems: Panorama and State-of-the-Art , year=

    Aminifar, Farrokh and Fotuhi-Firuzabad, Mahmud and Safdarian, Amir and Davoudi, Ali and Shahidehpour, Mohammad , journal=. Synchrophasor Measurement Technology in Power Systems: Panorama and State-of-the-Art , year=

    work page

  38. [38]

    MATPOWER: Steady-State Operations, Planning, and Analysis Tools for Power Systems Research and Education , year=

    Zimmerman, Ray Daniel and Murillo-Sánchez, Carlos Edmundo and Thomas, Robert John , journal=. MATPOWER: Steady-State Operations, Planning, and Analysis Tools for Power Systems Research and Education , year=

    work page

  39. [39]

    Thurner and A

    L. Thurner and A. Scheidler and F. Schafer and J. H. Menke and J. Dollichon and F. Meier and S. Meinecke and M. Braun , journal=. pandapower - an Open Source Python Tool for Convenient Modeling, Analysis and Optimization of Electric Power Systems , year=

    work page

  40. [40]

    Energies , volume =

    Ahmed, Muhammad Musadiq and Amjad, Muhammad and Qureshi, Muhammad Ali and Imran, Kashif and Haider, Zunaib Maqsood and Khan, Muhammad Omer , title =. Energies , volume =. 2022 , number =

    work page 2022

  41. [41]

    Integer linear programs for the power dominating set problem with channel limitation , journal =

    Mauro Lucci and Diego. Integer linear programs for the power dominating set problem with channel limitation , journal =. 2025 , issn =

    work page 2025