An FPRAS for two terminal reliability in directed acyclic graphs

2023/10/02 by Feng, Weiming, Guo, Heng
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2310.00938

Abstract

We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing problem of approximating two terminal unreliability in DAGs is #BIS-hard.

Related

• A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Estimation of Small s-t Reliabilities in Acyclic Networks
• Roots of Two-Terminal Reliability
• Robustification of the PC-Algorithm for Directed Acyclic Graphs