ND26 M INIMUM B ICONNECTIVITY A UGMENTATION

       
• I NSTANCE : Graph and a symmetric weight function .
• S OLUTION : A connectivity augmenting set E' for G , i.e., a set E' of unordered pairs of vertices from V such that is biconnected.
• M EASURE : The weight of the augmenting set, i.e., .

• Good News: Approximable within 2 [ 113 ] and [ 228 ].
• Comment: The same bound is valid also when G' must be bridge connected (edge connected) [ 228 ]. Minimum k -Connectivity Augmentation, the problem in which G' has to be k -connected (vertex or edge connected), is also approximable within 2 [ 219 ]. If the weight function satisfies the triangle inequality, the problem is approximable within 3/2 [ 114 ]. If the problem is the same as weighted M INIMUM K -V ERTEX C ONNECTED S UBGRAPH .
• Garey and Johnson: ND18