Adjiashvili, Hommelsheim and M\”uhlenthaler (AHM, in IPCO 2020), introduced a new and “natural” model of network design called flexible graph connectivity: given a multi-graph G=(V,E) with non-negative costs on the edges and a partition of E into a set of safe edges and a set of unsafe edges, find a cheapest connected spanning subgraph H=(V,F) of G that stays connected even after the failure of one unsafe edge (that is, H-e is connected for each unsafe edge e in F). Recent research has focused on approximation algorithms for this model and its extensions, and this has raised perplexing questions. The talk will cover the AHM model and its extensions, as well as some approximation algorithms for these models.

Time permitting, the second part of the talk will survey recent results on approximation algorithms for key special cases of the minimum-cost 2-edge connected spanning subgraph problem, focusing on the Matching Augmentation Problem (MAP).