  Network reliability is an important metric to evaluate the connectivity among
given vertices in uncertain graphs. Since the network reliability problem is
known as #P-complete, existing studies have used approximation techniques. In
this paper, we propose a new sampling-based approach that efficiently and
accurately approximates network reliability. Our approach improves efficiency
by reducing the number of samples based on stratified sampling. We
theoretically guarantee that our approach improves the accuracy of
approximation by using lower and upper bounds of network reliability, even
though it reduces the number of samples. To efficiently compute the bounds, we
develop an extended BDD, called S2BDD. During constructing the S2BDD, our
approach employs dynamic programming for efficiently sampling possible graphs.
Our experiment with real datasets demonstrates that our approach is up to 51.2
times faster than the existing sampling-based approach with higher accuracy.
