The probabilistic minimum vertex-covering problem

An instance of the probabilistic vertex-covering problem is a pair (G = (V, E), Pr) obtained by associating with each vertex υi ∈ V an ‘occurrence’ probability pi. We consider a modification strategy M transforming a vertex cover C for G into a vertex cover CI for the subgraph of G induced by a vertex-set I ⊆ V. The objective for the probabilistic vertex-covering is to determine a vertex cover of G minimizing the sum, over all subsets I ⊆ V, of the products: probability of I times CI. In this paper, we study the complexity of optimally solving probabilistic vertex-covering.