Jiong Guo: Improved Algorithms and Complexity for Power Domination in Graphs

The Power Dominating Set problem is a variant of the classical domination problem in graphs:

Given an undirected graph G=(V,E), find a minimum subset P of V such that all vertices in V are "observed" by vertices in P.

Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. Answering an open question of Haynes et al., we show that Power Dominating Set can be solved by "bounded-treewidth dynamic programs". Moreover, we simplify and extend several of their NP-completeness results, additionally showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. In particular, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and cannot be better approximated than Dominating Set.