Approximation Algorithms and Hardness for Domination with Propagation

Abstract

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. Note that rule (1) is the same as for the dominating set problem, and that rule (2) is a type of propagation rule that applies iteratively. We use n to denote the number of nodes. We show a hardness of approximation threshold of $2^{\log^{1-\epsilon}{n}}$ in contrast to the logarithmic hardness for dominating set. This is the first result separating these two problem. We give an $O(\sqrt{n})$ approximation algorithm for planar graphs, and show that our methods cannot improve on this approximation guarantee. We introduce an extension of PDS called ℓ-round PDS; for ℓ= 1 this is the dominating set problem, and for ℓ ≥ n − 1 this is the PDS problem. Our hardness threshold for PDS also holds for ℓ-round PDS for all ℓ ≥ 4. We give a PTAS for the ℓ-round PDS problem on planar graphs, for $\ell=O(\frac{\log{n}}{\log{\log{n}}})$. We study variants of the greedy algorithm, which is known to work well on covering problems, and show that the approximation guarantees can be Θ(n), even on planar graphs. Finally, we initiate the study of PDS on directed graphs, and show the same hardness threshold of $2^{\log^{1-\epsilon}{n}}$ for directed acyclic graphs.