  The power dominating set (PDS) problem is the following extension of the
well-known dominating set problem: find a smallest-size set of nodes $S$ that
power dominates all the nodes, where a node $v$ is power dominated if (1) $v$
is in $S$ or $v$ has a neighbor in $S$, or (2) $v$ has a neighbor $w$ such that
$w$ and all of its neighbors except $v$ are power dominated. We show a hardness
of approximation threshold of $2^{\log^{1-\epsilon}{n}}$ in contrast to the
logarithmic hardness for the dominating set problem. We give an $O(\sqrt{n})$
approximation algorithm for planar graphs, and show that our methods cannot
improve on this approximation guarantee. Finally, we initiate the study of PDS
on directed graphs, and show the same hardness threshold of
$2^{\log^{1-\epsilon}{n}}$ for directed \emph{acyclic} graphs. Also we show
that the directed PDS problem can be solved optimally in linear time if the
underlying undirected graph has bounded tree-width.

Computational Complexity;Discrete Mathematics