An Efficient Algorithm for Computing Network Reliability in Small Treewidth
Amir Kafshdar Goharshady Fatemeh Mohammadi
math.CO cs.DM math.PR








IST Austria (Institute of Science and Technology Austria)
Am Campus 1, 3400 Klosterneuburg, Austria
 amir.goharshady@ist.ac.at


School of Mathematics, University of Bristol
University Walk, Bristol, BS8 1TW, United Kingdom

fatemeh.mohammadi@bristol.ac.uk



	We consider the classic problem of Network Reliability. A network is given together with a source vertex, one or more target vertices, and probabilities assigned to each of the edges. Each edge appears in the network with its associated probability and the problem is to determine the probability of having at least one source-to-target path. This problem is known to be NP-hard.
	
	We present a linear-time fixed-parameter algorithm based on a parameter called treewidth, which is a measure of tree-likeness of graphs. Network Reliability was already known to be solvable in polynomial time for bounded treewidth, but there were no concrete algorithms and the known methods used complicated structures and were not easy to implement. We provide a significantly simpler and more intuitive algorithm that is much easier to implement.
	
	We also report on an implementation of our algorithm and establish the applicability of our approach by providing experimental results on the graphs of subway and transit systems of several major cities, such as London and Tokyo. To the best of our knowledge, this is the first exact algorithm for Network Reliability that can scale to handle real-world instances of the problem.  




Network Reliability, Fixed-parameter Algorithms, Tree Decomposition, Treewidth, FPT







§ INTRODUCTION


Network Reliability. Consider a network modeled as a graph G = (V, E), where each edge e ∈ E has a known probability of failure. For example, the graph might be a model of communication links in a mobile network or railway lines between subway stations. Given a source vertex  and a set  of target vertices, the goal of the Network Reliability problem is to assess the reliability of connections between  and . Concretely, the Network Reliability problem asks for the probability of existence of at least one source-to-target path that does not pass through failed edges. In the examples mentioned above, this is equivalent to asking for the probability of being able to send a message from  to  through the mobile network or the probability of being able to travel from  to  in the subway network.

Short History. Network reliability is an important and well-studied problem with surveys appearing as early as 1983 <cit.>. Aside from the obvious applications such as the two mentioned above, the problem has many other surprising applications, including analysis and elimination of redundancy in electronic systems and electrical power networks <cit.>. 
Network Reliability was shown to be NP-hard for general graphs <cit.> and hence researchers turned to solving it in special cases <cit.>, such as series-parallel graphs <cit.> and graphs with limited number of cuts <cit.>. Genetic <cit.>, randomized <cit.>, approximate <cit.> and Monte Carlo <cit.> algorithms are studied extensively as well. There are also several algebraic studies of the problem with the goal of obtaining bounds in series-parallel and other special families of graphs <cit.>. Several variants of the problem are defined <cit.>, and approaches to modify the network for its optimization are also investigated <cit.>. In this paper, we consider a parameterization of Network Reliability and obtain a linear-time algorithm. 

Parameterized Algorithms. An efficient parameterized algorithm solves an  optimization problem in polynomial time with respect to the size of input, but possibly with non-polynomial dependence on a specific aspect of the input's structure, which is called a “parameter" <cit.>. A problem that can be solved by an efficient parameterized algorithm is called fixed-parameter tractable (FPT). For example, there is a polynomial-time algorithm for computing minimal cuts in graphs whose runtime is exponentially dependent on the size of the resulting cut <cit.>. Exploiting the additional benefit of having a parameter, parameterized complexity provides finer detail than classical complexity theory <cit.>. 

Treewidth. A well-studied parameter for graphs is the treewidth, which is a measure of tree-likeness of graphs <cit.>. Many hard problems are shown to have efficient solutions when restricted to graphs with small treewidth <cit.>. Notably, <cit.> introduces a general framework that shows several variants of the network reliability problem can be solved in polynomial time when parameterized by the treewidth.
Many real-world graphs happen to have
small treewidth <cit.>. In this work, we show that subway and transit networks often have this property.

Our contribution. Our contribution is providing a new fixed-parameter algorithm for finding the exact value of Network Reliability, using treewidth as the parameter. Our algorithm, while being linear-time, is much shorter and simpler than the general framework utilized in <cit.>. We also provide an implementation of our algorithm and experimental results over the graphs of subway networks of several major cities. To the best of our knowledge, this is the first algorithm for finding the exact value of Network Reliability that can scale to handle real-world instances, i.e. subway and transit networks of major cities.


Graphs with constant treewidth are the most general family of networks for which exact algorithms for computing reliability are found. This family contains trees, series-parallel graphs and outerplanar graphs <cit.>.

Structure of the Paper. The present paper is organized as follows: First, Section <ref> provides formal definitions of the Network Reliability problem and Treewidth. Then, Section <ref>, which is the main part of the paper, presents our simple linear algorithm for solving Network Reliability in graphs with constant treewidth. Section <ref> contains a report of our implementation, which is publicly available, and establishes the applicability of our approach by providing experimental results on real-world subway networks.



§ PRELIMINARIES
 

In this section, we formalize our notation, and define the problem of Network Reliability and the notion of treewidth.

Multigraphs. A multigraph is a pair G = (V, E) where V is a finite set of vertices and E is a finite multiset of edges, i.e. each e ∈ E is of the form {u, v} for u, v ∈ V. The vertices u and v are called the endpoints of e. Note that E might contain distinct edges that have the same endpoints. In the sequel, we only consider multigraphs and simply call them graphs for brevity.

Notation. Given a graph G = (V, E), a path from u ∈ V to w ∈ V is a finite sequence u=u_0, u_1, …, u_l=w of distinct vertices such that for every i<l, there exists an edge e = {u_i, u_i+1}∈ E. We write u _G w to denote the existence of a path from u to w in G. We simply write u  w if G can be deduced from the context. For a set E' ⊆ E, we write u _E' w if there exists a path from u to w whose every edge is in E'. A connected component of a graph G is a maximal subset  C ⊆ V such that for every c_1, c_2 ∈ C, we have c_1 _G c_2. The graph G is called connected if it has exactly one connected component. A cycle in the graph G is a sequence w_0, w_1, …, w_l of vertices with l>0, such that for every i<l, there exists an edge e = {w_i, w_i+1}∈ E and all w_i are distinct except that w_0 = w_l. A graph is called a forest if it has no cycles. A forest is called a tree if it is connected. In other words, a tree is a connected graph with no cycles.

Network Reliability Problem.
A Network Reliability problem instance is a tuple I = (G, , , ) where G = (V, E) is a connected multigraph, ∈ V is a “source” vertex and ⊆ V a set of “target” vertices.  is a function of the form : E →[0, 1] which assigns a probability to every edge of the graph G. The reliability problem on instance I is then defined as follows: A new graph G^s is probabilistically constructed such that its vertex set is V and each edge e ∈ E appears in it with probability (e). Appearance of the edges are stochastic and independent of each other. The Network Reliability problem asks for the probability (I) of having at least one path from the source vertex  to a target vertex ∈ in G^s.

Remark. We are describing our approach on undirected graphs. However, it is straightforward to change all the steps of the algorithm to handle direcetd graphs as well.

We now provide a quick overview of the basics of tree decompositions and treewidth. A much more involved treatment can be found in <cit.>.

Tree Decompositions.
Given a connected multigraph G = (V, E), a tree T = (, E_T)  with vertex set  and edge set E_T is called a tree decomposition of G if the following four conditions hold:

	
  * Each vertex b ∈ of the tree T has an assigned set of vertices V(b)⊆ V. To distinguish vertices of T and G, we call each vertex of T a bag. 
	
  * Each vertex appears in some bag, i.e. ⋃_b ∈ V(b)=V.
	
  * Each edge appears in some bag, i.e. ∀ e = {u, v}∈ E  ∃ b ∈ s.t. {u, v}⊆ V(b). We denote the set of edges that appear in a bag b with E(b). Note that an edge appears in b if and only if both of its vertices do.
	
  * Each vertex v ∈ V appears in a connected subtree of T. More precisely, we let _v to be the set of bags whose vertex sets contain v, then _v must be a connected subtree of T.






See Figure <ref> for an example.
A rooted tree decomposition is a tree decomposition in which a unique bag
is specified as “root". Given two bags b and b', we say that b is an ancestor of b' if b appears in the unique path from the root to b'. In this case, we say that b' is a descendant of b. Note that each bag is both an ancestor and a descendant of itself. The bag b is called the parent of b' if it is an ancestor of b' and has an edge to b', i.e. {b, b'}∈ E_T. In this case, we say that b' is a child of b. A bag b with no children is called a leaf.

Treewidth. If a tree decomposition T has bags of size at most k+1, then it is called a k-decomposition or a decomposition of width k. The treewidth of a graph G is defined as the smallest k for which a k-decomposition of G exists. Intuitively, the treewidth of a graph measures how tree-like it is and graphs with smaller treewidth are more similar to trees.

Cut Property. Tree decompositions are important for algorithm design because removing the vertices of each bag b from the original graph G cuts it into connected components corresponding to the subtrees formed in T by removing b <cit.>. We call this the “cut property” and it allows bottom-up dynamic programming algorithms to operate on tree decompositions almost the same way as in trees <cit.>. We use this property in our algorithm in Section <ref>. We now formalize this point: 

Separators. Given a graph G = (V, E) and two sets of vertices A, B ⊆ V, we call the pair (A, B) a separation of G if (i) A ∪ B = V, and (ii) no edge connects a vertex in A ∖ B to a vertex in B ∖ A. We call A ∩ B the separator corresponding to the separation (A, B).

 
	Let T = (, E_T) be a tree decomposition of the graph G and let e = {a, b}∈ E_T be an edge of T. By removing e, T breaks into two connected components, T^a and T^b, respectively containing a and b. Let A = ⋃_t ∈ T^a V(t) and B = ⋃_t ∈ T^b V(t). Then (A, B) is a separation of G with separator V(a) ∩ V(b).




For example, consider the same graph as in Figure <ref>. By removing the edge from {2, 3, 5} to {2, 6, 7}, the tree decomposition breaks into two connected components, containing the vertices A = {2, 6, 7 } and B = { 1, 2, 3, 4, 5 }, respectively. This is a separation of the graph with separator {2}. These points are illustrated in Figure <ref>.


Computing a Tree Decomposition. In our algorithm in Section <ref>, when we operate on a graph G with n vertices and constant treewidth, we assume that we are also given a tree decomposition of G as part of the input. This is justified by an algorithm of Bodlaender <cit.>, that given a graph G and a constant k, decides in linear time whether G has treewidth at most k and if so, produces a k-decomposition of G with O(n · k) bags. 





§ ALGORITHM FOR NETWORK RELIABILITY
 

In this section, we provide an algorithm for solving instances
of the Network Reliability problem on graphs based on their tree decompositions.

Specification. The
input to the algorithm is a Network Reliability instance I = (G, , ,  ) together with a k-decomposition T = (, E_T) of the graph G. The output is the
reliability (I), i.e. the probability of existence of a path from  to . Given that
the tree decomposition can be rooted at any bag, without loss of generality,
we assume that the source vertex  is in the root bag. We also assume that G has n vertices and ||∈ O(n · k). This can be obtained by an algorithm described in <cit.>. 


Methodology. Our algorithm is based on a technique called “kernelization” <cit.>: Using the tree-decomposition T, we repeatedly shrink the graph G to obtain smaller graphs that all have the same reliability as G. We continue our shrinking until we reach a graph that has very few vertices, i.e. at most O(k) vertices. We then use brute force to compute the reliability of this graph.

Discrete Probability Distributions. Given a finite set X, a probability distribution over X is a function : X → [0, 1], that assigns a probability to each member of X, such that ∑_x∈ X(x) = 1.

We first define an extension of the Network Reliability problem, in which the probabilities of appearance of the edges need not be independent anymore, i.e. some edges are correlated. Although this extension makes the problem more general, it helps in finding a solution. As we will later see, it allows us to apply a shrinking procedure as described above.

Extended Network Reliability. An Extended Network Reliability instance with r parts is a tuple I = (G, E_1,  …, E_r, , , _1, …, _r) in which:


	
  * G = (V, E) is a connected graph;
	
  * The E_i's are pairwise disjoint multisets of edges and ⋃_i=1^r E_i = E;
	
  * ∈ V is the source vertex;
	
  * ⊆ V is the set of target vertices; and
	
  * Each _i: 2^E_i→ [0, 1] is a probability distribution over the subsets of E_i. 
	


We now define the Extended Network Reliability problem on the instance I as follows: a new graph G^s is probabilistically constructed such that its vertex set is V and its edge set is a subset  E^s ⊆ E chosen probabilistically as follows:

	
  * For every part E_i, a subset E^s_i ⊆ E_i of edges is probabilistically chosen according to the distribution _i. The E^s_i's are chosen independently of each other.
	
  * The set E^s is defined as E^s = ⋃_i=1^r E^s_i.

The Extended Network Reliability problem asks for the probability (I) that the probabilistically-constructed graph G^s contains a path from  to . Intuitively, appearance of every edge in each part E_i is correlated to every other edge in E_i, but independent of all the edges outside of E_i. A Network Reliability instance is simply an Extended Network Reliability instance in which each E_i consists of a single edge, i.e. every edge is independent of every other edge.

We now provide a simple brute force algorithm for the Extended Network Reliability problem. This algorithm will later serve as a subprocedure in our main algorithm.

The Brute Force Algorithm. Consider an Extended Network Reliability instance I as above and a graph G' = (V, E') where E' ⊆ E, i.e. a graph with the same set of vertices as G, but only a subset of its edges. We can easily compute (G^s = G'), i.e. the probability that the probabilistically-constructed graph G^s is equal to G'. We use each _i to find the probability of the specific combination of correlated edges that are present in E' ∩ E_i. Therefore, we have:

    (G^s = G') = ∏_i=1^r_i(E' ∩ E_i).

Now (I) is simply the sum of (G^s = G') over those graphs G' in which there is a path from  to . Hence, we can use the brute force method as in Algorithm <ref> for answering the Extended Network Reliability problem. The algorithm creates all possible subgraphs G' and checks if there is a path from  to  in G'. If so, it computes the probability (G^s = G'). Finally, it returns the sum of computed probabilities. 



Complexity of the Brute Force Algorithm. Assuming that the graph G has n vertices and m edges, Algorithm <ref> considers at most 2^m different cases for E' (Line 2). In each case, checking reachability (Line 4) can be done in O(m) using standard algorithms such as DFS or BFS, and computing (G^s = G'), i.e. the variable p in the algorithm (Lines 5–7), also takes O(m) time.  Hence, Algorithm <ref> has a total runtime of O(m · 2^m) which is exponential. Therefore, this algorithm is only applicable to very small graphs.

In order to use Algorithm <ref> on larger graphs, we need to shrink them to smaller graphs with the same reliability. The following lemmas are our main tools in doing so.

 
	Let G_B = (B, E_B) be a graph,  a set of target vertices, B^* ⊆ B a subset of vertices that contains a target vertex ^* ∈. Also, let E^* be the set of all possible edges over B^*, i.e. E^* = {{u, v} |  u, v ∈ B^* }. Then, there exists a function f : 2^E_B→ 2^E^* that maps every subset E' of edges of E_B to a subset f(E') of edges of E^*, such that:
	
		
  * For all a ∈ B^*, we have a _f(E') if and only if a _E'.
		
  * For all a, b ∈ B^* such that a _E' and b _E', we have a _f(E') b if and only if a _E' b.
		
  * For all a, b ∈ B^* such that a _E' and b _E', we have a _f(E') b.
	  
	Moreover, given E', one can compute f(E') in linear time, i.e. O(| B | + | E_B |).


Intuitively, the lemma above says that from a graph with vertex set B, one can create a smaller “digest” graph with vertex set B^* ⊆ B, in which (i) a vertex has a path to a target if and only if it used to have a path to a target in the first place, (ii) any two vertices that do not have a path to a target are in the same connected component if and only if they used to be in the same connected component in the first place, and (iii) all the vertices that can reach a target are put in the same connected component. Indeed, the construction below merges all the vertices that could originally reach a target into a single connected component, and keeps the other connected components intact. 


	We assume an arbitrary total order on the vertices so that given a set of vertices, we can talk of the vertex with the smallest index.
	We construct f(E') as follows:
	
		
  * For every vertex a ∈ B^* ∖{^* } such that a _E', we add the edge {a, ^* } to f(E').
		
  * We consider the connected components C_1, C_2, …, C_s of the graph (B, E'). For every C_i, if C_i ∩ = ∅ and C_i ∩ B^* ≠∅, we let c_i be the vertex in C_i ∩ B^* with the smallest index. For every vertex c'_i ∈ C_i ∩ B^* ∖{c_i}, we add the edge {c_i, c'_i} to f(E'). 
	
	Figure <ref> shows an example application of f.
	
	
	
	By the above construction, it is easy to verify that f(E') has the desired properties. Moreover, f(E') can be computed by a single use of a classical reachability algorithm, such as DFS, that finds the connected components C_i. Hence, it can be computed in O(| B | + | E_B |).


 
	Let I = (G, E_1, …, E_r, , , _1, …, _r) be an Extended Network Reliability instance such that:
	
		
  * G = (V, E) and (A, B) is a separation of G;
		
  * ∈ A;
		
  * There exists a target vertex ^* ∈ A ∩ B ∩;
		
  * Every part E_i is either entirely in A or entirely in B. Without loss of generality, we assume that E_1, …, E_t are entirely in A and E_t+1, …, E_r are entirely in B. We define E_A := E_1 ∪⋯∪ E_t and E_B := E_t+1∪⋯∪ E_r. If an E_i is entirely in A ∩ B, we consider it to be part of E_B;
	
	then, there exists a smaller instance I = (G, E_1, …, E_t, E_t+1, _1, …, _t, _t+1) with vertex set A, i.e. G = (A, E), such that (I)=(I).


Intuitively, given a few conditions, this lemma provides a way of shrinking an instance by means of decreasing the number of vertices in the instance, i.e. removing all the vertices in B ∖ A, without changing the reliability. 


	We use the function f as in Lemma <ref>, by considering B^* = A ∩ B and G_B = (B, E_t+1∪⋯∪ E_r) = (B, E_B). We let the new part E_t+1 = E^* consist of all the possible edges over B^*. We define the probability distribution _t+1: 2^E_t+1→ [0, 1] as follows. For every F ⊆E_t+1, we let 
	
    _t+1(F) := ∑_E' ∈ f^-1(F)∏_i=t+1^r _i(E' ∩ E_i).

	
	Claim.  Let E'_A ⊆ E_A and E'_B ⊆ E_B, we claim that _E'_A ∪ E'_B if and only if _E'_A ∪ f(E'_B).
	
	Proof of Claim. Note that B^* = A ∩ B is a separator in G, so there is no edge between A ∖ B and B ∖ A. Consider the graphs G_1 = (A ∪ B, E'_A ∪ E'_B) and G_2 = (A, E'_A ∪ f(E'_B)), we want to prove that _G_1 if and only if _G_2. 
	
	First, we assume s _G_1. Consider a path π := u_0, u_1, …, u_l in G_1 from u_0 = to some target vertex u_l ∈. We construct a path π' from  to  in G_2 by following π step-by-step. At each step, we assume that we have a prefix of π' from  to u_i. We extend this prefix as follows:
	
		
  * If the edge {u_i, u_i+1} is in E'_A, then it has appeared in both G_1 and G_2. So we simply extend π' by adding u_i+1. In particular, this case always happens if at least one of u_i and u_i+1 are in A ∖ B.
		
  * Otherwise, if both u_i and u_i+1 are in A ∩ B, then by Lemma <ref>, we have u_i _f(E'_B) u_i+1. So, we extend π' by a path from u_i to u_i+1 in f(E'_B).
		
  * Otherwise, if u_i ∈ A ∩ B and u_i+1∈ B ∖ A, then we consider two cases:
		
			
  * if the path π ends in a target vertex in B ∖ A without coming back to A ∩ B, then by Lemma <ref>, we have u_i _f(E'_B)^*. We extend π' by adding the path from u_i to ^*.
			
  * otherwise, π re-enters A ∩ B. Assume that this re-entry happens at u_j for some j>i+1. Then, by Lemma <ref>, we have u_i _f(E'_B) u_j. So, we extend π' with the path from u_i to u_j in f(E'_B) and continue from u_j.
		
		
	
	Note that no other case is possible, given that A ∩ B is a separator. Also, following the steps above, we either end up at ^* or u_l, both of whom are target vertices. Therefore _G_2. The other side can be proven similarly, i.e. by taking a path in G_2 and replacing every contiguous sequence of edges in f(E'_B) by edges in E'_B.
	
	
	We now continue our proof of the shrinking lemma. We prove that (I) = (I). We have 
	
    (I) = ∑_E' ⊆ E(G^s = (V, E')) ·δ(_E' )

	where δ is the indicator function that has a value of 1 if its parameter is true and 0 otherwise, i.e. δ(p) = {
	1     p
 
	0     p
	.. Therefore, if we consider E'_A = E' ∩ E_A and E'_B = E' ∩ E_B, we have:
	
    (I)  = ∑_E'_A ⊆ E_A∑_E'_B ⊆ E_B(G^s = (V, E'_A ∪ E'_B)) ·δ(_E'_A ∪ E'_B )

	
	We now divide the second summand based on the value of f(E'_B), to get:
	
	
    (I) =  ∑_E'_A ⊆ E_A∑_F ⊆E_t+1∑_E'_B ∈ f^-1(F)(G^s = (V, E'_A ∪ E'_B)) ·δ(_E'_A ∪ E'_B )

	
	The appearance of edges in E_A and E_B are independent of each other, so we have (G^s = (V, E'_A ∪ E'_B)) = (G^s ∩ E_A = E'_A) ·(G^s ∩ E_B = E'_B), therefore:
	
    (I) =  ∑_E'_A ⊆ E_A∑_F ⊆E_t+1∑_E'_B ∈ f^-1(F)(G^s ∩ E_A = E'_A) ·(G^s ∩ E_B = E'_B) ·δ(_E'_A ∪ E'_B )

	
	Given that (G^s∩ E_A = E'_A) is independent of the two inner summations, we have:
	
    (I) =  ∑_E'_A ⊆ E_A(G^s ∩ E_A = E'_A) ·∑_F ⊆E_t+1∑_E'_B ∈ f^-1(F)(G^s ∩ E_B = E'_B) ·δ(_E'_A ∪ E'_B )

	
	Moreover, appearance of edges in each E_i is independent of every other E_j, so (G^s ∩ E_A = E'_A) = ∏_i=1^t _i(E'_A ∩ E_i) and similarly, (G^s ∩ E_B = E'_B) = ∏_i=t+1^r _i(E'_B ∩ E_i). Therefore, we have:
	
    (I) = ∑_E'_A ⊆ E_A∏_i=1^t_i(E'_A ∩ E_i) ·∑_F ⊆E_t+1∑_E'_B ∈ f^-1(F)∏_i=t+1^r _i(E'_B ∩ E_i) ·δ(_E'_A ∪ E'_B )

	
	According to the Claim proven in Page claim, we have δ(_E'_A ∪ E'_B) = δ(_E'_A ∪ f(E'_B) ). Note that f(E'_B) is simply F, given that E'_B ∈ f^-1(F). So, we have: 
	
    (I) =  ∑_E'_A ⊆ E_A∏_i=1^t_i(E'_A ∩ E_i) ·∑_F ⊆E_t+1∑_E'_B ∈ f^-1(F)∏_i=t+1^r _i(E'_B ∩ E_i) ·δ(_E'_A ∪ F )

	
	In Equation (<ref>), we defined _t+1(F) as  ∑_E' ∈ f^-1(F)∏_i=t+1^r _i(E' ∩ E_i), therefore:
	
    (I) = ∑_E'_A ⊆ E_A∏_i=1^t_i(E'_A ∩ E_i) ·∑_F ⊆E_t+1_t+1 (F) ·δ(_E'_A ∪ F )

	
	We now reverse all the steps above, using G^s, i.e. the probabilistic graph obtained according to the Extended Network Reliability instance I:
	
	
    [l]
    	(I)     =    ∑_E'_A ⊆ E_A(G^s∩ E_A = E'_A) ·∑_F ⊆E_t+1(G^s∩E_t+1 = F)  ·δ(_E'_A ∪ F) 
        =    ∑_E'_A ⊆ E_A∑_F ⊆E_t+1(G^s∩ E_A = E'_A) ·(G^s∩E_t+1 = F)  ·δ(_E'_A ∪ F) 
        =    ∑_E'_A ⊆ E_A∑_F ⊆E_t+1(G^s = (V, E'_A ∪ F)) ·δ(_E'_A ∪ F) 
        =    ∑_E'⊆ E_A ∪E_t+1(G^s = (V, E'))  ·δ(_E') 
        =    (I).




The Complexity of Shrinking Lemma. To apply the Shrinking Lemma, we compute f(E'_B) for every E'_B ⊆ E_B. There are 2^| E_B | such subsets. Moreover, by Lemma <ref>, each computation of f takes O(| B | + | E_B |), therefore the overall complexity of the Shrinking Lemma is O(2^| E_B |· (| B | + | E_B |)), which is exponential in the size of E_B. Hence, the Shrinking Lemma should only be applied when the set B is small. In our algorithm below, whenever we use the Shrinking Lemma, the set B is a bag of the tree decomposition and therefore has size at most O(k).

The following lemma provides the last ingredient for our main algorithm:
 
	Let I = (G, E_1, …, E_r, , , _1, …, _r) be an Extended Network Reliability instance with r ≥ 2. There exists an instance I_r-1,r = (G, E_1, …, E_r-2, E_r+1, , , _1, …, _r-2, _r+1) such that (I) = (I_r-1, r). We refer to I_r-1, r as the instance obtained by merging E_r-1 and E_r in I. 



	Let W ⊆ V be the subset of vertices consisting of all the endpoints of edges in E_r-1 and E_r. We define E_r+1 as a set containing all possible edges over W, i.e. E_r+1 = {{u, v} |  u, v ∈ W }. Let F_r-1⊆ E_r-1 and F_r⊆ E_r, we define F_r-1⊕ F_r as the subset of E_r+1 that contains an edge from u to v if at least one of F_r and F_r+1 do. Intuitively, F_r-1⊕ F_r is a special kind of union that ignores repeated edges with the same endpoints. For every F_r+1⊆ E_r+1, we define
	
    _r+1(F_r+1) := ∑_F_r-1⊕ F_r = F_r+1_r-1(F_r-1) ·_r(F_r).

	Informally, we took two parts E_r-1 and E_r which used to be independent and merged them into a single correlated part. It is straightforward to verify that this construction preserves the reliability.


Note that the order of E_i's in I does not matter. Hence, we can define I_i,j as the instance obtained by merging E_i and E_j in I and construct it in a similar manner.


We are now ready to present our main algorithm for computing Network Reliability when the underlying graph has a small treewidth k. Basically, our algorithm applies the Shrinking Lemma repeatedly until the number of vertices in the graph is reduced to O(k). Then, it runs the brute force algorithm over it.


Input. As mentioned earlier, the input to the algorithm is a Network Reliability instance I = (G, , ,  ) together with a k-decomposition T = (, E_T) of the graph G rooted at a bag r ∈ that contains the source vertex, i.e. ∈ V(r). 

Our Algorithm. We compute (I) as follows:

	
  * We take an arbitrary target vertex ^* ∈ and add it to the vertex set of every bag in . 
	
  * As long as  contains more than one bag, we do the following:
	
		
  * We take an arbitrary leaf bag b ∈. Let p be the parent bag of b. 
		
  * We apply the Shrinking Lemma with (A, B) = (⋃_a ∈∖{b} V(a) , V(b)). This effectively removes all the vertices in B ∖ A from G.
		
  * We remove b from T.
		
  * We take all the edge parts E_i_1, E_i_2, …, E_i_j that are entirely in V(p) and merge them together using Lemma <ref>.
	
	
  * If  contains a single bag r, we simply run the brute force algorithm on V(r) for computing (I).

Consider the graph depicted in Figure <ref> with arbitrary probabilities. We assume = 1 and = { 7 }. Therefore, in Step (1), we add 7 to every bag. Figure <ref> shows the iterations of Step (2), i.e. each panel shows one application of shrinking and merging. The figure does not show the probabilities. In each iteration, a leaf bag b with parent p is chosen, it is removed from the tree decomposition and the vertices that only appeared in b are deleted from the graph. Moreover, a new edge part is added that covers all possible edges between the vertices in the intersection of V(b) and V(p). It is then merged with the already existing edge parts of V(b). This process continues until only one bag r (the root) remains. At this point, the brute force algorithm is used to compute the reliability.




	The algorithm above correctly computes (I).



	Each iteration of Step 2 above reduces the number of bags by one, hence the algorithm terminates. We show that the reliability is preserved after each iteration of Step 2. We also show that before and after each iteration of Step 2, for every correlated edge part E_i, there exists a bag b_E_i∈ such that every endpoint of every edge in E_i is in V(b_E_i). Note that initially, each E_i consists of a single edge and hence this property holds by definition of tree decompositions.
	
	In Step 2(b), we can apply the Shrinking Lemma because (i) (A, B) is a separation of G by the Cut Property (Lemma <ref>); (ii) ∈ V(r) ⊆ A; (iii) ^* ∈ A ∩ B ∩ because ^* is in the vertex set of every bag; and (iv) for every edge part E_i, there exists a bag such that E_i is entirely in that bag. As shown in Page lemma:shrink, Shrinking Lemma preserves the reliability. Moreover, by Lemma <ref>, we have A ∩ B = V(p) ∩ V(b) and therefore the newly added edge part is entirely in A ∩ B ⊆ V(p). Finally, by Lemma <ref>, merging edge parts in Step 2(d) does not change the reliability.
	
	It follows by an easy induction that the reliability is preserved when we reach Step 3. At this point, (I) is computed by the brute force algorithm. Hence, our algorithm computes (I) correctly.


Complexity of Our Algorithm. The algorithm applies the shrinking lemma O(n · k) times and in each time we have | B |≤ k+2 and | E_B |≤ (k+2) · (k+1). Hence, the overall runtime for the calls to shrinking lemma is O(n · k^3 · 2^(k+2)(k+1)). Similarly, the algorithm performs O(n · k) merge operations, each of which on two parts of size at most 2^k+22. Hence each merge operation takes at most O(k^2 · 2^(k+2)(k+1)) and the overall runtime for merging is also O(n · k^3 · 2^(k+2)(k+1)). Finally, the algorithm runs the brute force procedure on a graph with at most k+22 edges, which takes O(k^2 · 2^k+22) time. All the other operations are performed in linear time. Hence the total runtime of our algorithm is O(n · k^3 · 2^(k+2)(k+1)), which depends linearly on n and exponentially on k. Hence, we have the following theorem:


	There exists a linear-time fixed-parameter algorithm for solving Network Reliability when parameterized by the treewidth, i.e. when the treewidth is a small constant.


Pseudocode. Our approach is summarized in Algorithm <ref>.












§ IMPLEMENTATION AND EXPERIMENTAL RESULTS
 

We implemented our approach in Java. Our code is available at <https://ist.ac.at/ akafshda/reliability>. We used a tool called FlowCutter <cit.> for computing the tree decompositions. FlowCutter applies a state-of-the-art heuristic algorithm to find tree decompositions of small width. However, it is not guaranteed to find an optimal tree decomposition. In each case, we limited FlowCutter to a maximum runtime of 10 minutes.

We experimented with the subway networks of several major cities, including Berlin, London, Tehran, Tokyo and Vienna. Table <ref> provides a summary of the instances. Notably, it shows that all of these major subway networks have a small treewidth. In each case, we set the source and target vertices as the subway stations next to some of the major universities. Specifically:

	
  * In Berlin, we used the Technical University of Berlin (Ernst-Reuter-Platz) as the source and the Freie University (Thielplatz) and the Humboldt University (Friedrichstrasse) as the targets.
	
  * In London, we used the London School of Economics (Holborn) as the source and the King's College (Temple), Imperial College (South Kensington) and University College London (Euston Square) as the targets.
	
  * In Tehran, we used Amirkabir University (Teatr-e Shahr) as the source and Sharif University (Daneshgah-e Sharif), University of Tehran (Meydan-e Enqelab) and the Iran University of Science and Technology (Daneshgah-e Elm o San'at) as the targets.
	
  * In Tokyo, we used the University of Tokyo (Okachimachi) as the source and Keio University (Mita) and Waseda University (Waseda) as the targets.
	
  * In Vienna, we used the University of Vienna (Schottenring) as the source and the Technical University of Vienna (Karlsplatz) as the target.


In our experiments, we assumed that every edge of the network appears with the same probability p. We provide experimental results for different values of p between 0 and 1 with step size 0.05. Note that this is not a requirement of our algorithm, which can handle different probability values for different edges. However, we did not have access to the failure probabilities of the connections in the subway networks, given that such information is classified in most countries. 



As shown in Table <ref>, our algorithm is extremely efficient and, in all these real-world cases, answers the Network Reliability problem in just a few seconds. In contrast, previous exact approaches such as <cit.> could only handle academic examples with less than 10 vertices. Figure <ref> provides a summary of our experimental results.





§ CONCLUSION

In this paper, on the theoretical side, we presented a linear-time algorithm for computing Network Reliability on graphs with small treewidth. Our algorithm uses the concept of kernelization, i.e. it repeatedly transforms an instance into a smaller one with the same reliability. On the experimental side, we showed that subway networks of several major cities have small treewidth and hence our algorithm can be applied to them. We also demonstrated that our algorithm is extremely efficient and can handle these real-world instances in a few seconds, while previous exact methods could only handle academic examples with a handful of edges.




Acknowledgments.
The research was partially supported by the EPSRC Early Career Fellowship EP/R023379/1, Grant № SC7-1718-01 of the London Mathematical Society, an IBM PhD Fellowship, and a DOC Fellowship of the Austrian Academy of Sciences (ÖAW).



§ REFERENCES


36
	natexlab#1#1
	
	
	
	
	
	
	
	
	
	[#1],#1
	[Agrawal and Barlow(1984)]reliabilitySurvey
	authorA. Agrawal, authorR. E. Barlow,
	titleA survey of network reliability and domination
		theory,
	journalOperations Research volume32
	(year1984) pages478–492.
	
	[Moore and Shannon(1956)]reliabilityApplication
	authorE. F. Moore, authorC. E. Shannon,
	titleReliable circuits using less reliable relays,
	journalJournal of the Franklin Institute
	volume262 (year1956) pages191–208.
	
	[Ball(1986)]ball1986computational
	authorM. O. Ball,
	titleComputational complexity of network reliability
		analysis: An overview,
	journalIEEE Transactions on Reliability
	volume35 (year1986) pages230–239.
	
	[Satyanarayana and Wood(1985)]satyanarayana1985linear
	authorA. Satyanarayana, authorR. K. Wood,
	titleA linear-time algorithm for computing k-terminal
		reliability in series-parallel networks,
	journalSIAM Journal on Computing volume14
	(year1985) pages818–832.
	
	[Provan and Ball(1984)]provan1984computing
	authorJ. S. Provan, authorM. O. Ball,
	titleComputing network reliability in time polynomial in
		the number of cuts,
	journalOperations Research volume32
	(year1984) pages516–526.
	
	[Coit and Smith(1996)]coit1996reliability
	authorD. W. Coit, authorA. E. Smith,
	titleReliability optimization of series-parallel systems
		using a genetic algorithm,
	journalIEEE Transactions on reliability
	volume45 (year1996) pages254–260.
	
	[Karger(2001)]karger2001randomized
	authorD. R. Karger,
	titleA randomized fully polynomial time approximation
		scheme for the all-terminal network reliability problem,
	journalSIAM review volume43
	(year2001) pages499–522.
	
	[Srivaree-ratana et al.(2002)Srivaree-ratana, Konak, and
		Smith]srivaree2002estimation
	authorC. Srivaree-ratana, authorA. Konak,
	authorA. E. Smith,
	titleEstimation of all-terminal network reliability using
		an artificial neural network,
	journalComputers & Operations Research
	volume29 (year2002) pages849–868.
	
	[Gertsbakh and Shpungin(2016)]gertsbakh2016models
	authorI. B. Gertsbakh, authorY. Shpungin,
	titleModels of network reliability: analysis, combinatorics, and
		Monte Carlo, publisherCRC press, year2016.
	
	[Brown et al.(1996)Brown, Colbourn, and Wagner]brown1996cohen
	authorJ. I. Brown, authorC. J. Colbourn,
	authorD. G. Wagner,
	titleCohen–macaulay rings in network reliability,
	journalSIAM Journal on Discrete Mathematics
	volume9 (year1996) pages377–392.
	
	[Mohammadi(2016)]fm2016combinatorial
	authorF. Mohammadi,
	titleCombinatorial and geometric view of the system
		reliability theory,
	in: booktitleInternational Congress on Mathematical
		Software, organizationSpringer, year2016, pp.
	pages148–153.
	
	[Sáenz-de Cabezón and Wynn(2015)]saenz2015hilbert
	authorE. Sáenz-de Cabezón, authorH. P. Wynn,
	titleHilbert functions in design for reliability,
	journalIEEE transactions on reliability
	volume64 (year2015) pages83–93.
	
	[Mohammadi et al.(2016)Mohammadi, Sáenz-de Cabezón, and
		Wynn]mohammadi2016algebraic
	authorF. Mohammadi, authorE. Sáenz-de Cabezón,
	authorH. P. Wynn,
	titleThe algebraic method in tree percolation,
	journalSIAM Journal on Discrete Mathematics
	volume30 (year2016) pages1193–1212.
	
	[Mohammadi(2016)]mohammadi2016divisors
	authorF. Mohammadi,
	titleDivisors on graphs, orientations, syzygies, and
		system reliability,
	journalJournal of Algebraic Combinatorics
	volume43 (year2016) pages465–483.
	
	[Guidotti et al.(2017)Guidotti, Gardoni, and
		Chen]guidotti2017network
	authorR. Guidotti, authorP. Gardoni,
	authorY. Chen,
	titleNetwork reliability analysis with link and nodal
		weights and auxiliary nodes,
	journalStructural Safety volume65
	(year2017) pages12–26.
	
	[Zhang and Mahadevan(2017)]zhang2017game
	authorX. Zhang, authorS. Mahadevan,
	titleA game theoretic approach to network reliability
		assessment,
	journalIEEE Transactions on Reliability
	(year2017).
	
	[Yeh et al.(2015)Yeh, Bae, and Huang]yeh2015new
	authorW.-C. Yeh, authorC. Bae, authorC.-L.
		Huang,
	titleA new cut-based algorithm for the multi-state flow
		network reliability problem,
	journalReliability Engineering & System Safety
	volume136 (year2015) pages1–7.
	
	[Gutjahr et al.(1996)Gutjahr, Pflug, and
		Ruszczyński]gutjahr1996configurations
	authorW. J. Gutjahr, authorG. C. Pflug,
	authorA. Ruszczyński,
	titleConfigurations of series-parallel networks with
		maximum reliability,
	journalMicroelectronics Reliability volume36
	(year1996) pages247–253.
	
	[Niedermeier(2002)]niedermeier2002invitation
	authorR. Niedermeier,
	titleInvitation to fixed-parameter algorithms
	(year2002).
	
	[Cygan et al.(2015)Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk,
		Pilipczuk, and Saurabh]cygan2015parameterized
	authorM. Cygan, authorF. V. Fomin,
	authorŁ. Kowalik, authorD. Lokshtanov,
	authorD. Marx, authorM. Pilipczuk,
	authorM. Pilipczuk, authorS. Saurabh,
	titleParameterized algorithms, publisherSpringer,
	year2015.
	
	[Downey and Fellows(2012)]downey2012parameterized
	authorR. G. Downey, authorM. R. Fellows,
	titleParameterized complexity, publisherSpringer
		Science & Business Media, year2012.
	
	[Robertson and Seymour(1990)]robertson1990graph
	authorN. Robertson, authorP. D. Seymour,
	titleGraph minors. iv. tree-width and
		well-quasi-ordering,
	journalJournal of Combinatorial Theory, Series B
	volume48 (year1990) pages227–254.
	
	[Courcelle(1990)]courcelle1990monadic
	authorB. Courcelle,
	titleThe monadic second-order logic of graphs. i.
		recognizable sets of finite graphs,
	journalInformation and computation volume85
	(year1990) pages12–75.
	
	[Chatterjee et al.(2016)Chatterjee, Goharshady, Ibsen-Jensen, and
		Pavlogiannis]chatterjee2016algorithms
	authorK. Chatterjee, authorA. K. Goharshady,
	authorR. Ibsen-Jensen, authorA. Pavlogiannis,
	titleAlgorithms for algebraic path properties in
		concurrent systems of constant treewidth components,
	in: booktitleACM SIGPLAN Notices,
	volume volume51, organizationACM,
	year2016, pp. pages733–747.
	
	[Courcelle and Mosbah(1993)]courcelle1993monadic
	authorB. Courcelle, authorM. Mosbah,
	titleMonadic second-order evaluations on tree-decomposable
		graphs,
	journalTheoretical Computer Science volume109
	(year1993) pages49–82.
	
	[Chatterjee et al.(2019)Chatterjee, Goharshady, Okati, and
		Pavlogiannis]datapacking
	authorK. Chatterjee, authorA. K. Goharshady,
	authorN. Okati, authorA. Pavlogiannis,
	titleEfficient parameterized algorithms for data packing,
	journalProceedings of the ACM on Programming Languages
	volume3 (year2019) pages53.
	
	[Bodlaender(1988)]bodlaender1988dynamic
	authorH. L. Bodlaender,
	titleDynamic programming on graphs with bounded
		treewidth,
	in: booktitleInternational Colloquium on Automata,
		Languages, and Programming, organizationSpringer,
	year1988, pp. pages105–118.
	
	[Chatterjee et al.(2018)Chatterjee, Ibsen-Jensen, Goharshady, and
		Pavlogiannis]chatterjee2018algorithms
	authorK. Chatterjee, authorR. Ibsen-Jensen,
	authorA. K. Goharshady, authorA. Pavlogiannis,
	titleAlgorithms for algebraic path properties in
		concurrent systems of constant treewidth components,
	journalACM Transactions on Programming Languages and
		Systems (TOPLAS) volume40 (year2018)
	pages9.
	
	[Chatterjee et al.(2017)Chatterjee, Goharshady, Ibsen-Jensen, and
		Pavlogiannis]chatterjee2016Jtdec
	authorK. Chatterjee, authorA. K. Goharshady,
	authorR. Ibsen-Jensen, authorA. Pavlogiannis,
	titleJTDec: A tool for tree decompositions in soot,
	in: booktitleFifteenth International Symposium on
		Automated Technology for Verification and Analysis, ATVA,
	publisherSpringer, year2017.
	
	[Wolle(2002)]wolle2002framework
	authorT. Wolle,
	titleA framework for network reliability problems on
		graphs of bounded treewidth,
	journalLecture notes in computer science
	(year2002) pages137–149.
	
	[Bodlaender(1994)]bodlaender1994tourist
	authorH. L. Bodlaender,
	titleA tourist guide through treewidth,
	journalActa cybernetica volume11
	(year1994).
	
	[Thorup(1998)]thorup1998all
	authorM. Thorup,
	titleAll structured programs have small tree width and
		good register allocation,
	journalInformation and Computation volume142
	(year1998) pages159–181.
	
	[Gustedt et al.(2002)Gustedt, Mæhle, and
		Telle]gustedt2002treewidth
	authorJ. Gustedt, authorO. Mæhle,
	authorJ. Telle,
	titleThe treewidth of java programs,
	journalAlgorithm Engineering and Experiments
	(year2002) pages57–59.
	
	[Chatterjee et al.(2019)Chatterjee, Goharshady, and
		Goharshady]amirtr
	authorK. Chatterjee, authorA. K. Goharshady,
	authorE. K. Goharshady,
	titleThe treewidth of smart contracts,
	in: booktitleACM Symposium on Applied Computing (SAC),
	year2019.
	
	[Bodlaender(1996)]bodlaender1996linear
	authorH. L. Bodlaender,
	titleA linear-time algorithm for finding
		tree-decompositions of small treewidth,
	journalSIAM Journal on computing volume25
	(year1996) pages1305–1317.
	
	[Hamann and Strasser(2018)]hamann2018graph
	authorM. Hamann, authorB. Strasser,
	titleGraph bisection with pareto optimization,
	journalJournal of Experimental Algorithmics (JEA)
	volume23 (year2018).
	



