Residual reliability of P-threshold graphs (Q4936504)

Let \({\mathcal P}(G)\) be a set of connected subgraphs of a graph \(G\) and let, for each edge \(e\), its reliability \(p(e)\in [0,1]\) be defined. The residual reliability (RR) of \(G\) is the probability of the event that the set of residual edges forms an element of \({\mathcal P}(G)\). In the article under review, the problem of determining the RR is solved for several classes of \(P\)-threshold graphs which have previously been characterized in structural terms by means of the decomposition of graphs into primary components. Actually, linear-time algorithms are provided for all these classes. On the other hand, the author proves that this problem is \(\sharp P\)-complete even in the class of biregular graphs with the probability of failure of each edge equal to 1/2. This implies the same issue for the classes of indecomposable box-threshold and pseudo-threshold graphs.