2017/12/27 by Amir Kafshdar Goharshady, Fatemeh Mohammadi, Goharshady, Amir Kafshdar +1
Engineering · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Reliability and Maintenance Optimization
paper · pdf · doi:10.48550/arxiv.1712.09692
openalex publication_date 2017/12/27 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We consider the classic problem of Network Reliability. A network is given\ntogether with a source vertex, one or more target vertices, and probabilities\nassigned to each of the edges. Each edge appears in the network with its\nassociated probability and the problem is to determine the probability of\nhaving at least one source-to-target path. This problem is known to be NP-hard.\n We present a linear-time fixed-parameter algorithm based on a parameter\ncalled treewidth, which is a measure of tree-likeness of graphs. Network\nReliability was already known to be solvable in polynomial time for bounded\ntreewidth, but there were no concrete algorithms and the known methods used\ncomplicated structures and were not easy to implement. We provide a\nsignificantly simpler and more intuitive algorithm that is much easier to\nimplement.\n We also report on an implementation of our algorithm and establish the\napplicability of our approach by providing experimental results on the graphs\nof subway and transit systems of several major cities, such as London and\nTokyo. To the best of our knowledge, this is the first exact algorithm for\nNetwork Reliability that can scale to handle real-world instances of the\nproblem.\n