Reliability covering problems for hypergraphs (Q1968515): Difference between revisions

Given is a hypergraph \(G=(V, E)\), multiple edges are enabled and each edge \(e_{i}\in E\) can be excluded with equal probability \(1-p.\) The values of a reliability polynomial \(\text{Pol}(G,p)\) determine the probability of covering the set of nodes \(V\) \ by nonexcluded edges. The problem of evaluation of \(\text{Pol}(G,p)\) is called the reliability covering problem (RCP). The values of a reliability polynomial \(\text{Pol}_{C}(G,p)\) determine the probability that the graph \(G \) is connected (despite edges can be excluded). The problem of evaluation of \(\text{Pol}_{C}(G,p)\) is called reliability connected-covering problem (RCCP). It is mentioned that the problems are NP-complete and narrowing the problems to sets of multigraphs does not lead to substantial simplification. The goal of the paper is to obtain effectively computed estimates of RCP and RCCP for the general case. The shift operations of the first and of the second kind are investigated for hypergraphs and it is proved that they do not increase reliability coefficients of RCP and RCCP. The shift operations enable us to transform an arbitrary hypergraph into a multiregular one. Then it is proved that for multiregular hypergraphs reliability polynomials can be effectively computed. An example of such computations for canonical hypergraphs is given. The RCP and RCCP problems provide a general model of reliability of connections for general networks.