Exact Computation of Network Reliability with Sentential Decision Diagrams

Modern society largely depends on various network systems such as computer networks, communications, and power networks, it is crucial to exactly compute the reliability of these network systems. The exact computation of network reliability is known to be #P-Complete problem. The state-of-the-art exact computation method is based on binary decision diagrams (BDDs). Sentential decision diagrams (SDDs) are a new canonical representation of Boolean functions which is a strict superset of BDD. In both theoretical and practical perspectives, SDDs are a more compact representation than BDDs. In addition, it maintains canonicity and polynomial-time operations on Boolean functions. In this paper, we propose a top-down compilation algorithm based on SDD for representing the set of subgraphs that makes the network active. Then the exact computation of network reliability is based on the constructed SDD. The experiments show that in most real networks and all synthetic networks, the resulting SDD is smaller than the BDD representing the same set of subgraphs. Thus, SDD-based method to exact computation of network reliability is more efficient than BDD-based.