Master Thesis

My Master thesis is titled Reliability of Networks, and it tackles the problem of finding a maximum flow in networks with random capacities. The thesis was supervised by Prof. Martin Loebl.

The original version of the thesis can be found on the Charles University Digital Repository, or on Github. Minor typos have been fixed in the revised version on Github. The Github repository also contains the source code with a record of all changes made since the submitted version.

Abstract

Finding the maximum flow is one of the most fundamental problems of theoretical computer science, crucial both in countless practical applications, as well as in theoretical connections to other combinatorial problems. In the usual setting, the flow is found in a static, unchanging network. However, in the real world, failures can occur—pipes burst, wires fail, roads get blocked—often at random. In this thesis, we study how these failures affect the ability of the network to carry flow. We delve into the area of network reliability, analyze its combinatorial properties, show that it is hard to compute, and investigate how to approximate it. We define d-reliability as the probability that a network with randomly failing capacities enables a flow of size at least d. As the main result, we show that if the treewidth of the network and the demand we impose on the flow are bounded, then the d-reliability is computable efficiently.