Ghost Value Augmentation for k-Edge-Connectivity

We give a poly-time algorithm for the k-edge-connected spanning subgraph (k-ECSS) problem that returns a solution of cost no greater than the cheapest (k + 10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems.

Our guarantees improve upon the best-known approximation factor of 2 for k-ECSS whenever the optimal value of (k + 10)-ECSS is close to that of k-ECSS. This is a property that holds for the closely related problem k-edge-connected spanning multi-subgraph (k-ECSM), which is identical to k-ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a (1 + O( 1 /k))-approximation algorithm for k-ECSM, which resolves a conjecture of Pritchard and improves upon a recent (1 + O( 1 / √ k))-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k-ECSM, showing that our approximation ratio is tight up to the constant factor in O( 1 /k), unless P = NP.