DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.21

An Efficient Algorithm for Power Dominating Set

Authors: Thomas Bläsius and Max Göttlicher

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2023.21,
  author =	{Bl\"{a}sius, Thomas and G\"{o}ttlicher, Max},
  title =	{{An Efficient Algorithm for Power Dominating Set}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.21},
  URN =		{urn:nbn:de:0030-drops-186743},
  doi =		{10.4230/LIPIcs.ESA.2023.21},
  annote =	{Keywords: Power Dominating Set, Implicit Hitting Set, Parameterized Complexity, Reduction Rules}
}

Search Results

Documents authored by Göttlicher, Max

An Efficient Algorithm for Power Dominating Set

Abstract

Cite as

Thanks for your feedback!

Could not send message