Almost Tight Additive Guarantees for k-Edge-Connectivity

We consider the $\boldsymbol{k}$-edge connected spanning subgraph (k-ECSS) problem, where we are given an undirected graph $G=(V, E)$ with nonnegative edge costs $\left\{c_{e}\right\}_{e \in E}$, and the goal is to find a minimum-cost subgraph H of G that is k edge connected, i.e., there exist at least k edge-disjoint paths between every pair of vertices in H. For even k, we present a polynomial time algorithm that computes a ($k-2$)-edge connected subgraph of cost at most that of the optimal k-edge connected subgraph of G; for odd k, we obtain a $(k-3)$ edge connected subgraph of cost at most the optimum. In fact, the cost of our solution does not exceed the optimal value, $\mathbf{L P}_{\boldsymbol{k} \text {-ECSSLP }}^{\boldsymbol{*}}$ of the natural LP-relaxation for $\boldsymbol{k}$-ECSS. Since k-ECSS is $A P X$-hard for all values of $k \geq 2$, our results are nearly optimal. They also significantly improve upon the recent work of Hershkowitz, Klein, and Zenklusen [1], both in terms of solution quality and the simplicity of algorithm and its analysis. Interestingly, our techniques also yield an alternate guarantee, where we obtain a($k-1$)-edge connected subgraph of cost at most $1.5 \cdot \mathrm{LP}_{\boldsymbol{k}-\mathrm{ECSSLP}}^{*}$; with unit edge costs, the cost guarantee improves to $\left(1+\frac{4}{3 k}\right) \cdot$ LP $_{\boldsymbol{k} \text {-ECSSLP }}^{\boldsymbol{*}}$, which improves upon the state-of-the-art approximation guarantee for unit edge costs [2], albeit with a unit loss in edge connectivity. Our k-ECSS-result also yields results for the k-edge connected spanning multigraph (k-ECSM) problem, where multiple copies of an edge can be selected. For $\boldsymbol{k}$-ECSM, we obtain a $\left(1+\frac{2}{k}\right)$-approximation algorithm for even k, and $\mathbf{a}\left(1+\frac{3}{k}\right)$ approximation algorithm for odd $\boldsymbol{k}$. Finally, our techniques extend to the degree-bounded versions of k-ECSS and k-ECSM, wherein we also impose degree lower- and upper- bounds on the nodes. Our results for k-ECSS and k-ECSM extend to yield the same cost and connectivity guarantees for these degree-bounded versions with an additive violation of (roughly) 2 for the degree bounds. These are the first results for degree-bounded $\{k$-ECSS, k-ECSM $\}$ of the form where the cost of the solution obtained is at most the optimum, and the connectivity constraints are violated by an additive constant. Work done while N. Kumar was a postdoc in the $C \& O$ department at the University of Waterloo. Supported in part by C. Swamy’s NSERC Discovery grant.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.