New Algorithms for Network Connectivity and Reliability

Abstract

Network connectivity and reliability are fundamental topics in graph algorithms, with wide-ranging applications in the design and evaluation of real-world networks. These notions can be viewed as two complementary measures of robustness under link failures, corresponding respectively to worst-case failures and independently random failures. Although both areas have been studied extensively for decades, recent explosive growth in the size and complexity of application networks has shifted the algorithmic focus from the traditional polynomial-time efficiency to fast algorithms with running time near-linear in the size of the input.In this thesis, I present new algorithms for two major problems in these areas: connectivity augmentation and network unreliability. Connectivity augmentation is a fundamental network design problem whose goal is to increase the connectivity of a given network to a specified target value. The network unreliability problem asks for estimating the probability that a network becomes disconnected under independently random link failures. For both problems, the algorithms developed in this thesis achieve almost-linear running time, which is optimal up to sub-polynomial factors, improving substantially over the previous best-known quadratic-time algorithms. These results are obtained by combining ideas from prior work with new structural insights and novel techniques.This thesis also investigates extensions of these problems. I generalize the connectivity augmentation algorithm to the settings with Steiner connectivity requirements. For the network unreliability problem, I extend the model to hypergraphs and obtain the first nontrivial algorithm for hypergraph unreliability. This extension captures higher-order interactions that arise in networks with more complex relationships than pairwise connections.Taken together, these results significantly advance the state of the art in network connectivity and reliability, both by providing faster algorithms for long-standing problems and by introducing more general problem formulations that more accurately model real-world network interactions across a range of domains.