The Probabilistic Minimum Vertex‐covering Problem
Cécile Murat, Vangélis Th. Paschos · International Transactions in Operational Research · 2002
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 Μ 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.