Cover Small Cuts and Flexible Graph Connectivity Problems

Abstract

Given a graph with capacitated edges and a set of links on the same vertex set, the Cover Small Cuts problem aims to choose a minimum-cost link set such that for each cut with total edge capacity below a given threshold, at least one selected link covers that cut.

We present examples and analysis of the Cover Small Cuts problem, and cut covering problems on strongly pliable families, a subfamily of pliable families. Pliable set families require that for any two sets A, B in the family, at least two of A-B, B-A, A∪B, A∩B are also in the family. Strongly pliable set families require that for any two sets A, B in the family that cross, at least one of A-B, B-A is also in the family, and at least one of A∪B, A∩B is also in the family. Shortly before the submission of this thesis, we learned about prior work on what we call strongly pliable families; see Section 1.4.1 for further details. We decided to stay with the term "strongly pliable families" since it is consistent with the notion of "pliable families" introduced recently.

We present a family of Cover Small Cuts problems such that key property used to prove the approximation ratio of Jain's iterative rounding approximation algorithm does not hold. We show that families of “small cuts” are always strongly pliable, but not all strongly pliable families can be realized as families of small cuts. We prove a 5-approximation algorithm for cut covering problems on strongly pliable families using the primal-dual method of Williamson, Goemans, Vazirani, and Mihail. We compare strongly pliable families to other subfamilies of pliable families, such as uncrossable families. We also study some other cut covering problems.

In Flexible Graph Connectivity (FGC) problems, the edges of the input graph are partitioned into safe and unsafe edges. In real-world applications, safe edges represent reliable connections and unsafe edges represent connections that could break. We aim to select a minimum-cost set of edges that achieve given connectivity requirements despite the limitations of the unsafe edges. We present a constant-factor approximation algorithm for the (1, q)-FGC problem. We explore relaxations of the (p, q)-FGC problem that allow multiple copies of an edge to be selected, and construct approximation algorithms with better approximation ratios than those currently known for the (unrelaxed) (p, q)-FGC problem.

We end with a summary of Williamson et al.’s primal-dual approximation algorithm, a versatile approximation algorithm for cut covering problems including Cover Small Cuts; and our results from computational experiments on this algorithm.