Document Open Access Logo

An Efficient Algorithm for Power Dominating Set

Authors Thomas Bläsius , Max Göttlicher

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.21.pdf
  • Filesize: 1.05 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Karlsruhe Institute of Technology (KIT), Germany
Max Göttlicher
  • Karlsruhe Institute of Technology (KIT), Germany

Funding

  • Göttlicher, Max: German Research Foundation (DFG) as part of the Research Training Group GRK 2153: Energy Status Data - Informatics Methods for its Collection, Analysis and Exploitation.

Cite As Get BibTex

Thomas Bläsius and Max Göttlicher. An Efficient Algorithm for Power Dominating Set. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.21

Abstract

The problem Power Dominating Set (PDS) is motivated by the placement of phasor measurement units to monitor electrical networks. It asks for a minimum set of vertices in a graph that observes all remaining vertices by exhaustively applying two observation rules. Our contribution is twofold. First, we determine the parameterized complexity of PDS by proving it is W[P]-complete when parameterized with respect to the solution size. We note that it was only known to be W[2]-hard before. Our second and main contribution is a new algorithm for PDS that efficiently solves practical instances.
Our algorithm consists of two complementary parts. The first is a set of reduction rules for PDS that can also be used in conjunction with previously existing algorithms. The second is an algorithm for solving the remaining kernel based on the implicit hitting set approach. Our evaluation on a set of power grid instances from the literature shows that our solver outperforms previous state-of-the-art solvers for PDS by more than one order of magnitude on average. Furthermore, our algorithm can solve previously unsolved instances of continental scale within a few minutes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Power Dominating Set
  • Implicit Hitting Set
  • Parameterized Complexity
  • Reduction Rules

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Ashkan Aazami. Domination in graphs with bounded propagation: algorithms, formulations and hardness results. Journal of Combinatorial Optimization, 19:429-456, 2008. URL: https://doi.org/10.1007/s10878-008-9176-7.
  2. T. L. Baldwin, L. Mili, M. B. Boisen, and R. Adapa. Power system observability with minimal phasor measurement placement. IEEE Transactions on Power Systems, 8:707-715, 1993. URL: https://doi.org/10.1109/59.260810.
  3. Daniel Binkele-Raible and Henning Fernau. An exact exponential time algorithm for power dominating set. Algorithmica, 63(1):323-346, 2012. URL: https://doi.org/10.1007/s00453-011-9533-2.
  4. Thomas Bläsius and Max Göttlicher. An efficient algorithm for power dominating set, 2023. URL: https://arxiv.org/abs/2306.09870.
  5. Chassidy Bozeman, Boris Brimkov, Craig Erickson, Daniela Ferrero, Mary Flagg, and Leslie Hogben. Restricted power domination and zero forcing problems. Journal of Combinatorial Optimization, 37:935-956, 2018. URL: https://doi.org/10.1007/s10878-018-0330-6.
  6. Boris Brimkov, Derek Mikesell, and Logan Smith. Connected power domination in graphs. Journal of Combinatorial Optimization, 38(1):292-315, 2019. URL: https://doi.org/10.1007/s10878-019-00380-7.
  7. Dennis J. Brueni. Minimal pmu placement for graph observability: a decomposition approach. Master’s thesis, Virginia Polytechnic Institute and State University, 1993. URL: https://doi.org/10919/45368.
  8. Dennis J. Brueni and Lenwood S. Heath. The pmu placement problem. SIAM J. Discret. Math., 19:744-761, 2005. URL: https://doi.org/10.1137/S0895480103432556.
  9. Jiong Guo, Rolf Niedermeier, and Daniel Raible. Improved algorithms and complexity results for power domination in graphs. Algorithmica, 52(2):177-202, 2008. URL: https://doi.org/10.1007/s00453-007-9147-x.
  10. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL: https://www.gurobi.com.
  11. Teresa W Haynes, Sandra M Hedetniemi, Stephen T Hedetniemi, and Michael A Henning. Domination in graphs applied to electric power networks. SIAM journal on discrete mathematics, 15(4):519-529, 2002. URL: https://doi.org/10.1137/S0895480100375831.
  12. Mikoláš Janota and Joao Marques-Silva. Solving qbf by clause selection. In International Joint Conference on Artificial Intelligence, 2015. Google Scholar
  13. Raka Jovanovic and Stefan Voss. The fixed set search applied to the power dominating set problem. Expert Systems, 37(6):e12559, 2020. URL: https://doi.org/10.1111/exsy.12559.
  14. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. Parameterized power domination complexity. Information Processing Letters, 98(4):145-149, 2006. URL: https://doi.org/10.1016/j.ipl.2006.01.007.
  15. Chung-Shou Liao and Der-Tsai Lee. Power domination in circular-arc graphs. Algorithmica, 65(2):443-466, 2013. URL: https://doi.org/10.1007/s00453-011-9599-x.
  16. L. Mili, Thomas L. Baldwin, and R. Adapa. Phasor measurement placement for voltage stability analysis of power systems. 29th IEEE Conference on Decision and Control, pages 3033-3038 vol.6, 1990. URL: https://doi.org/10.1109/CDC.1990.203341.
  17. Paul Saikko, Jeremias Berg, and Matti Järvisalo. LMHS: A SAT-IP Hybrid MaxSAT Solver. In International Conference on Theory and Applications of Satisfiability Testing, 2016. URL: https://doi.org/10.1007/978-3-319-40970-2_34.
  18. Logan A. Smith and Illya V. Hicks. Optimal sensor placement in power grids: Power domination, set covering, and the neighborhoods of zero forcing forts, 2020. URL: https://arxiv.org/abs/2006.03460.
  19. L. Thurner, A. Scheidler, F. Schäfer, J. Menke, J. Dollichon, F. Meier, S. Meinecke, and M. Braun. pandapower - An open-source python tool for convenient modeling, analysis, and optimization of electric power systems. IEEE Transactions on Power Systems, 33(6):6510-6521, November 2018. URL: https://doi.org/10.1109/TPWRS.2018.2829021.
  20. Guangjun Xu, Liying Kang, Erfang Shan, and Min Zhao. Power domination in block graphs. Theoretical computer science, 359(1-3):299-305, 2006. URL: https://doi.org/10.1016/j.tcs.2006.04.011.
  21. Yixing Xu, Nathan P Myhrvold, Dhileep Sivam, Kaspar Mueller, Daniel Julius Olsen, Bainan Xia, Daniel Livengood, Victoria Hunt, Benjamin Rouill'e d'Orfeuil, Daniel B. C. Muldrew, Merrielle Ondreicka, and Megan Bettilyon. U.s. test system with high spatial and temporal resolution for renewable integration studies. 2020 IEEE Power & Energy Society General Meeting (PESGM), pages 1-5, 2020. URL: https://doi.org/10.1109/PESGM41954.2020.9281850.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact