The probabilistic minimum dominating set problem

We present a natural wireless sensor network problem, which we model as a probabilistic version of the min dominating set problem (called probabilistic min dominating set). We first show that calculation of the objective function of this general probabilistic problem is #P-complete. We then introduce a restricted version of probabilistic min dominating set and show that, this time, calculation of its objective function can be performed in polynomial time and that this restricted problem is “just” NP-hard, since it is a generalization of the classical min dominating set. We study the complexity of this restricted version in graphs where min dominating set is polynomial, mainly in trees and paths and then we give some approximation results for it.