Computing the K-terminal reliability of directed path graphs

• We study the problem of computing K-terminal reliability for two subclasses of chordal graphs.
• We show that computing the K-terminal reliability of a directed path graph is #P-complete.
• We propose an O(n2)O(n2)-time algorithm for computing the K-terminal reliability of a rooted directed path graph.

Let G   denote a graph, and K⊆V(G)K⊆V(G) represent a set of target vertices. Assume that the non-target vertices of G fail independently with given probabilities. The K-terminal reliability of G is defined as the probability that all target vertices in K are connected. Computing K-terminal reliability is #P-complete for chordal graphs, yet solvable in polynomial time for its subclass of interval graphs. While improving both of these results, this work demonstrates that although the problem remains #P-complete when restricted to directed path graphs, a further restriction to rooted directed path graphs yields a polynomial time solution.