Efficient Constructions Of Convex Combinations For 2-Edge-Connected Subgraphs On Fundamental Classes

We present coloring-based algorithms for tree augmentation and use them to construct convex combinations of 2-edge-connected subgraphs. This classic tool has been applied previously to the problem, but our algorithms illustrate its flexibility, which - in coordination with the choice of spanning tree - can be used to obtain various properties (e.g., 2-vertex connectivity) that are useful in our applications.We use these coloring algorithms to design approximation algorithms for the 2-edge-connected multigraph problem (2ECM) and the 2-edge-connected spanning subgraph problem (2ECS) on two well-studied types of LP solutions. The first type of points, half-integer square points, belong to a class of fundamental extreme points, which exhibit the same integrality gap as the general case. For half-integer square points, the integrality gap for 2ECM is known to be between 6/5 and 4/3. We improve the upper bound to 9/7. The second type of points we study are uniform points whose support is a 3-edge-connected graph and each entry is 2/3. Although the best-known upper bound on the integrality gap of 2ECS for these points is less than 4/3, previous results do not yield an efficient algorithm. We give the first approximation algorithm for 2ECS with ratio below 4/3 for this class of points. (C) 2021 Published by Elsevier B.V.