Abstract:
In this talk, I will discuss the Flexible Network Design model. In this non-uniform fault model, introduced by Adjiashvili, the edge set of a given graph is partitioned into safe and unsafe edges. A vertex pair (s,t) is (p,q)-flex-connected if s and t have p edge-connectivity even after the removal/failure of any q unsafe edges. The goal is to choose a min-cost subgraph H of a given graph G such that H has desired flex-connectivity for a given set of vertex pairs. This model generalizes the well-studied edge-connectivity based network design, however, even special cases are provably much harder to approximate.
The approximability of network design in this model has been mainly studied for two settings of interest: (i) single pair setting for (1,k) and (k,1) (ii) spanning setting under the name FGC (flexible graph connectivity). There have been several positive results in these papers. However, despite similarity to the well-known network design problems, this new model has been challenging to design approximation algorithms for, especially when p and q are at least 2. We obtain two results that advance our understanding of algorithm design in this model.
First, we give a 5-approximation for (2,2)-flex-connectivity in the single pair setting. Previously no non-trivial approximation was known for this setting. Second, for the spanning setting, we give an O(p)-approximation for (p,q)-FGC in the spanning setting for q = 2,3 for all p, and for q=4 when p is even. We also give an O(q)-approximation for (2,q)-FGC for all q. Our results are obtained via the augmentation framework where we identify a structured way to use the well-known 2-approximation for covering uncrossable families of cuts.
