Consider a probabilistic graph $G = (V, E)$ where each edge operates (exists) with probability $p$, independent of other edges. We consider a set $S \subseteq E$ to be a *state* of $G$. We say that $S$ *occurs* when each edge of $S$ operates, and all other edges fail (i.e., in $E \setminus S$). Define $\phi(S)$ to be 1 if $S$ operates, and 0 otherwise. We want to know: what is the probability that $G$ is in an operating state, under $\phi$?

The *reliability polynomial* is $\text{Rel}_\phi(G; p) = \sum_{S \subseteq E} \Pr[S\;\text{is operating}]\phi(S)$. What is interesting is calculating the coefficients of this polynomial.

Due to Valiant, in general this task is $\mathcal{\#P}$-complete. However, several classes of graphs are known to have this task be poly-time computable, such as cycles, series-parallel graphs, etc. 

Say that $\phi$ is *coherent* when if $S \subseteq T$, $\phi(S) \le \phi(T)$. Define $F_\phi = \{S \colon S \subseteq E, \phi(E\setminus S) = 1\}$, and $F_i = \{F \in F_\phi \colon |F| = i\}$. This is called the *$F$-form* of the reliability polynomial. Therefore, we can rewrite the polynomial as: $\text{Rel}_\phi(G;p) = \sum_{i=0}^m F_i(1-p)^ip^{m-i}$. 

What is known about $F$-forms? Suppose $|V| = n, |E| = m$. $F_i = 0$ for $i > n-m+1$, and if the smallest edge cutset has size $c$, $F_i = {m \choose i}$ for $i < c$. For any $k$, calculating $F_{c+k}$ runs in time exponential in $k$. By the Kirchoff Matrix Tree Theorem, $F_{m-n+1}$ is the number of spanning trees in the graph, which is poly-time computable. Once new coefficients are known, the bounds on the remaining ones become tighter.

Open questions:

 1. Can we compute the number of spanning connected subgraphs with exactly 1 cycle in poly-time? This can be done for planar graphs. (this would be the coefficient $F_{m-n}$).
 2. What is the complexity of the decision problem $\{<G, H>\;\vert\;\text{Rel}(G; p) \ge \text{Rel}(H; p)\;\text{for all $0 \le p \le 1$}\}$? It doesn't even appear to be in $\mathcal{NP}$.