Polynomial-time algorithms for 2-edge-connected subgraphs on fundamental classes by top-down coloring
share
Finding the exact integrality gap α for the LP relaxation of the 2-edge-connected spanning multigraph problem (2EC) is closely related to the same problem for the Held-Karp relaxation of the metric traveling salesman problem (TSP). While the former problem seems easier than the latter, since it is less constrained, currently the upper bounds on the respective integrality gaps for the two problems are the same. An approach to proving integrality gaps for both of these problems is to consider fundamental classes of extreme points. For 2EC, better bounds on the integrality gap are known for certain important special cases of these fundamental points. For example, for half-integer square points, the integrality gap is between 6/5 and 4/3. Our main result is to improve the approximation factor to 9/7 for 2EC for these points. Our approach is based on constructing convex combinations and our key tool is the top-down coloring framework for tree augmentation, recently introduced by Iglesias and Ravi, whose flexibility we employ to exploit beneficial properties in both the initial spanning tree and in the input graph. We also show how these tools can be tailored to the closely related problem of uniform covers for which the proofs of the best-known bounds do not yield polynomial-time algorithms. A key ingredient here is to use a particular convex combination spanning trees guaranteed by a rainbow spanning tree decomposition, recently used by Boyd and Sebo.
READ FULL TEXT