{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T09:01:36Z","timestamp":1764061296751,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T00:00:00Z","timestamp":1734912000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T00:00:00Z","timestamp":1734912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2153:  Energy Status Data - Informatics Methods for its Collextion, Analysis and Exploitation"],"award-info":[{"award-number":["GRK 2153:  Energy Status Data - Informatics Methods for its Collextion, Analysis and Exploitation"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The problem <jats:sc>Power Dominating Set<\/jats:sc> (<jats:sc>PDS<\/jats:sc>) 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 <jats:sc>PDS<\/jats:sc> by proving it is <jats:italic>W<\/jats:italic>[<jats:italic>P<\/jats:italic>]-complete when parameterized with respect to the solution size. We note that it was only known to be <jats:italic>W<\/jats:italic>[2]-hard before. Our second and main contribution is a new algorithm for <jats:sc>PDS<\/jats:sc> that efficiently solves practical instances. Our algorithm consists of two complementary parts. The first is a set of reduction rules for <jats:sc>PDS<\/jats:sc> 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 <jats:sc>PDS<\/jats:sc> by more than one order of magnitude on average. Furthermore, our algorithm can solve previously unsolved instances of continental scale within a few minutes.<\/jats:p>","DOI":"10.1007\/s00453-024-01283-8","type":"journal-article","created":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T13:49:51Z","timestamp":1734961791000},"page":"344-376","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Efficient Algorithm for Power Dominating Set"],"prefix":"10.1007","volume":"87","author":[{"given":"Thomas","family":"Bl\u00e4sius","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max","family":"G\u00f6ttlicher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,23]]},"reference":[{"key":"1283_CR1","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10878-008-9176-7","volume":"19","author":"A Aazami","year":"2008","unstructured":"Aazami, A.: Domination in graphs with bounded propagation: algorithms, formulations and hardness results. J. Comb. Optim. 19, 429\u2013456 (2008). https:\/\/doi.org\/10.1007\/s10878-008-9176-7","journal-title":"J. Comb. Optim."},{"key":"1283_CR2","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/59.260810","volume":"8","author":"TL Baldwin","year":"1993","unstructured":"Baldwin, T.L., Mili, L., Boisen, M.B., Adapa, R.: Power system observability with minimal phasor measurement placement. IEEE Trans. Power Syst. 8, 707\u2013715 (1993). https:\/\/doi.org\/10.1109\/59.260810","journal-title":"IEEE Trans. Power Syst."},{"issue":"1","key":"1283_CR3","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00453-011-9533-2","volume":"63","author":"D Binkele-Raible","year":"2012","unstructured":"Binkele-Raible, D., Fernau, H.: An exact exponential time algorithm for power dominating set. Algorithmica 63(1), 323\u2013346 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9533-2","journal-title":"Algorithmica"},{"key":"1283_CR4","doi-asserted-by":"publisher","unstructured":"Bl\u00e4sius, T., G\u00f6ttlicher, M.: An efficient algorithm for power dominating set. In: Li-G\u00f8rtz, I., Farach-Colton, M., Puglisi, S.J., Herman, G. (eds.) 31st Annual European Symposium on Algorithms, ESA 2023, September 4\u20136, 2023, Amsterdam, The Netherlands. volume 274 of LIPIcs. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum f\u00fcr, pp. 21:1\u201321:15. Informatik, New York (2023). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.21","DOI":"10.4230\/LIPICS.ESA.2023.21"},{"key":"1283_CR5","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1007\/s10878-018-0330-6","volume":"37","author":"C Bozeman","year":"2018","unstructured":"Bozeman, C., Brimkov, B., Erickson, C., Ferrero, D., Flagg, M., Hogben, L.: Restricted power domination and zero forcing problems. J. Comb. Optim. 37, 935\u2013956 (2018). https:\/\/doi.org\/10.1007\/s10878-018-0330-6","journal-title":"J. Comb. Optim."},{"issue":"3","key":"1283_CR6","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/j.ejor.2018.09.030","volume":"273","author":"B Brimkov","year":"2019","unstructured":"Brimkov, B., Fast, C.C., Hicks, I.V.: Computational approaches for zero forcing and related problems. Eur. J. Oper. Res. 273(3), 889\u2013903 (2019)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1283_CR7","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/s10878-019-00380-7","volume":"38","author":"B Brimkov","year":"2019","unstructured":"Brimkov, B., Mikesell, D., Smith, L.: Connected power domination in graphs. J. Comb. Optim. 38(1), 292\u2013315 (2019). https:\/\/doi.org\/10.1007\/s10878-019-00380-7","journal-title":"J. Comb. Optim."},{"key":"1283_CR8","unstructured":"Brueni, D.J.: Minimal PMU placement for graph observability: a decomposition approach (1993) http:\/\/hdl.handle.net\/10919\/45368"},{"key":"1283_CR9","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1137\/S0895480103432556","volume":"19","author":"DJ Brueni","year":"2005","unstructured":"Brueni, D.J., Heath, L.S.: The PMU placement problem. SIAM J. Discret. Math. 19, 744\u2013761 (2005). https:\/\/doi.org\/10.1137\/S0895480103432556","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1283_CR10","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/INCO.1995.1156","volume":"123","author":"LM Cai","year":"1995","unstructured":"Cai, L.M., Chen, J., Downey, R., Fellows, M.: On the structure of parameterized problems in NP. Inf. Comput. 123(1), 38\u201349 (1995). https:\/\/doi.org\/10.1006\/INCO.1995.1156","journal-title":"Inf. Comput."},{"key":"1283_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, vol. 4. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"2","key":"1283_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00453-007-9147-x","volume":"52","author":"J Guo","year":"2008","unstructured":"Guo, J., Niedermeier, R., Raible, D.: Improved algorithms and complexity results for power domination in graphs. Algorithmica 52(2), 177\u2013202 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9147-x","journal-title":"Algorithmica"},{"key":"1283_CR13","unstructured":"Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual (2023). https:\/\/www.gurobi.com"},{"issue":"4","key":"1283_CR14","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"TW Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discrete Math. 15(4), 519\u2013529 (2002). https:\/\/doi.org\/10.1137\/S0895480100375831","journal-title":"SIAM J. Discrete Math."},{"key":"1283_CR15","unstructured":"Janota, M., Marques-Silva, J.: Solving QBF by clause selection. In: International Joint Conference on Artificial Intelligence (2015)"},{"issue":"6","key":"1283_CR16","doi-asserted-by":"publisher","DOI":"10.1111\/exsy.12559","volume":"37","author":"R Jovanovic","year":"2020","unstructured":"Jovanovic, R., Voss, S.: The fixed set search applied to the power dominating set problem. Expert Syst. 37(6), e12559 (2020). https:\/\/doi.org\/10.1111\/exsy.12559","journal-title":"Expert Syst."},{"issue":"4","key":"1283_CR17","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.ipl.2006.01.007","volume":"98","author":"J Kneis","year":"2006","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Parameterized power domination complexity. Inf. Process. Lett. 98(4), 145\u2013149 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2006.01.007","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1283_CR18","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00453-011-9599-x","volume":"65","author":"C-S Liao","year":"2013","unstructured":"Liao, C.-S., Lee, D.-T.: Power domination in circular-arc graphs. Algorithmica 65(2), 443\u2013466 (2013). https:\/\/doi.org\/10.1007\/s00453-011-9599-x","journal-title":"Algorithmica"},{"key":"1283_CR19","doi-asserted-by":"publisher","unstructured":"Mili, L., Baldwin, T, Adapa, R.: Phasor measurement placement for voltage stability analysis of power systems. In: 29th IEEE Conference on Decision and Control, vol.6, pp. 3033\u20133038 (1990). https:\/\/doi.org\/10.1109\/CDC.1990.203341","DOI":"10.1109\/CDC.1990.203341"},{"issue":"12","key":"1283_CR20","doi-asserted-by":"publisher","first-page":"4423","DOI":"10.1016\/j.laa.2011.05.012","volume":"436","author":"DD Row","year":"2012","unstructured":"Row, D.D.: A technique for computing the zero forcing number of a graph with a cut-vertex. Linear Algebra Appl. 436(12), 4423\u20134432 (2012)","journal-title":"Linear Algebra Appl."},{"key":"1283_CR21","doi-asserted-by":"publisher","unstructured":"Saikko, P., Berg, J., J\u00e4rvisalo, M.: LMHS: A SAT-IP hybrid MaxSAT solver. In: International Conference on Theory and Applications of Satisfiability Testing (2016). https:\/\/doi.org\/10.1007\/978-3-319-40970-2_34","DOI":"10.1007\/978-3-319-40970-2_34"},{"key":"1283_CR22","unstructured":"Smith, L.A., Hicks, I.V.: Optimal sensor placement in power grids: power domination, set covering, and the neighborhoods of zero forcing forts. arXiv, arXiv:2006.03460 (2020)"},{"issue":"6","key":"1283_CR23","doi-asserted-by":"publisher","first-page":"6510","DOI":"10.1109\/TPWRS.2018.2829021","volume":"33","author":"L Thurner","year":"2018","unstructured":"Thurner, L., Scheidler, A., Sch\u00e4fer, F., Menke, J., Dollichon, J., Meier, F., Meinecke, S., Braun, M.: pandapower\u2014an open-source python tool for convenient modeling, analysis, and optimization of electric power systems. IEEE Trans. Power Syst. 33(6), 6510\u20136521 (2018). https:\/\/doi.org\/10.1109\/TPWRS.2018.2829021","journal-title":"IEEE Trans. Power Syst."},{"issue":"1\u20133","key":"1283_CR24","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.tcs.2006.04.011","volume":"359","author":"G Xu","year":"2006","unstructured":"Xu, G., Kang, L., Shan, E., Zhao, M.: Power domination in block graphs. Theor. Comput. Sci. 359(1\u20133), 299\u2013305 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.04.011","journal-title":"Theor. Comput. Sci."},{"key":"1283_CR25","doi-asserted-by":"publisher","unstructured":"Xu, Y., Myhrvold, N., Sivam, D., Mueller, K., Olsen, D., Xia, B., Livengood, D., Hunt, V., d\u2019Orfeuil, B.R., Muldrew, D., Ondreicka, M., Bettilyon, M.: U.S. test system with high spatial and temporal resolution for renewable integration studies. In: IEEE Power and Energy Society General Meeting (PESGM), pp. 1\u20135 (2020). https:\/\/doi.org\/10.1109\/PESGM41954.2020.9281850","DOI":"10.1109\/PESGM41954.2020.9281850"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01283-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01283-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01283-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T08:49:16Z","timestamp":1740041356000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01283-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,23]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1283"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01283-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,12,23]]},"assertion":[{"value":"6 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}