Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity

Abstract

We present improved approximation algorithms for some problems in the related areas of Capacitated Network Design and Flexible Graph Connectivity. In the Cap-$k$-ECSS problem, we are given a graph $G=(V,E)$ whose edges have non-negative costs and positive integer capacities, and the goal is to find a minimum-cost edge-set $F$ such that every non-trivial cut of the graph $G^{\prime }=(V,F)$ has capacity at least $k$. We present an $O(\log k)$-approximation algorithm for the Cap-$k$-ECSS problem, asymptotically improving upon the previous best approximation ratio of $\min (O(\log n),O(k))$ whenever $\log (k)=o(\log n)$, where $n$ denotes $|V|$. (See section 1, for a detailed discussion.) In the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)$-FGC, the input is a graph $G(V,E)$ where $E$ is partitioned into safe and unsafe edges, and the goal is to find a minimum cost set of edges $F$ such that the subgraph $G^{\prime }(V,F)$ remains $p$-edge connected upon removal of any $q$ unsafe edges from $F$. We design a $7$-approximation algorithm for the $(1,q)$-FGC problem, improving on the previous best approximation ratio of $(q+1)$. Both of our results are obtained by using natural LP relaxations strengthened with the knapsack-cover inequalities, and then, during the rounding process, utilizing a recent $O(1)$-approximation algorithm for the CoverSmallCuts problem. In the latter problem, the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than a specified value is covered by a link. We also show that the problem of covering small cuts inherently arises in another variant of $(p,q)$-FGC. Specifically, we give Cook reductions that preserve approximation ratios within $O(1)$ factors between the $(2,q)$-FGC problem and the 2-CoverSmallCuts problem; in the latter problem, each small cut needs to be covered by two links.

Prelim version in ICALP 2025, https://doi.org/10.4230/LIPIcs.ICALP.2025.20