Bicriteria Approximation for k-Edge-Connectivity

A graph is $k$-edge-connected if it contains $k$ edge-disjoint paths between any two nodes. We consider the following problem.

$k$-Edge-Connected Spanning Subgraph ($k$-ECSS)
Input: A (multi-)graph $G=(V,E)$ with edge costs and an integer $k$.
Output: A min-cost $k$-edge-connected spanning subgraph $J$ of $G$.

The problems admits approximation ratio $2$ by a reduction to a bidirected graph (c.f. [17]), and no better approximation ratio is known. Recently, Hershkowitz, Klein, and Zenklusen [14] (henceforth HKZ) gave a bicriteria $(1,k-10)$-approximation algorithm that computes a $(k-10)$-edge-connected spanning subgraph of cost at most the optimal value of a standard Cut-LP for $k$-ECSS. Our first result improves the connectivity approximation to $k-4$.

The $k$-Edge-Connected Spanning Multi-subgraph ($k$-ECSM) problem is almost the same as $k$-ECSS, except that any edge can be selected multiple times at the same cost. For $k$-ECSM, approximation ratios $3/2$ for $k$ even and $3/2+O(1/k)$ for $k$ odd were known long time ago [10, 11], and it was conjectured by Pritchard [29] that $k$-ECSM admits approximation ratio $1+O(1/k)$. HKZ [14] showed that $k$-ECSM has an $\left(1+\mathrm{\Omega }(1/k)\right)$-approximation threshold and that a $(1,k-p)$ bicriteria approximation for $k$-ECSS w.r.t. the standard Cut-LP implies approximation ratio $1+p/k$ for $k$-ECSM. Thus the novel result of HKZ [14] implies an approximation ratio $1+10/k$ for $k$-ECSM (improving the previous ratio $1+O(1/\sqrt{k})$ of [16]), and we reduce the approximation ratio to $1+4/k$.

In addition, we also study bicriteria approximation ratios when the cost approximation is bellow $2$, and prove the following.

We note that while HKZ presented a novel original approach for attacking the problem and gave the first additive bicriteria approximation, our contribution here is more modest, as follows.

• $\mathrm{■}$

  We present a simpler algorithm that uses the HKZ [14] idea and a much simpler proof, based on new properties of $k$-ECSS Cut-LP extreme point solutions; see Lemmas 4.

• $\mathrm{■}$

  This enabled us to improve the connectivity approximation from $k-10$ to $k-4$.

• $\mathrm{■}$

  We use the same idea to present another nontrivial bicriteria approximation $(3/2,k-2)$.

We now survey some related work. $k$-ECSS is an old fundamental problem in combinatorial optimization and network design. The case $k=1$ is the MST problem, while for $k=2$ the problem is MAX-SNP hard even for unit costs [7]. Pritchard [29] showed that there is a constant $ϵ>0$ such that for any $k\ge 2$, $k$-ECSS admits no $(1+ϵ)$-approximation algorithm, unless P = NP. No such hardness of approximation was known for $k$-ECSM, and Pritchard [29] conjectured that $k$-ECSM admits approximation ratio $1+O(1/k)$. This conjecture was resolved by HKZ [14], who also proved a matching hardness of approximation result.

The $k$-ECSS problem and its special cases have been extensively studied, c.f [22, 8, 10, 11, 18, 1, 4, 17, 13, 12, 29, 30, 32, 14] for only a small sample of papers in the field. Nevertheless, the current best known approximation ratio for $k$-ECSS is $2$, the same as was four decades ago. The $2$-approximation is obtained by bidirecting the edges of $G$, computing a min-cost directed spanning subgraph that contains $k$ edge-disjoin dipaths to all nodes from some root node (this can be done in polynomial time [5]), and returning its underlying graph. A $2$-approximation can also be achieved with the iterative rounding method [15], that gives a $2$-approximation also for the more general Steiner Network problem, where we seek a min-cost subgraph that contains $r_{uv}$ edge-disjoint paths for every pair of nodes $u,v\in V$. The directed version of $k$-ECSS was also studied, c.f. [5, 13, 1, 17], and for this case also no better than $2$-approximation is known, except for special cases.

Bicriteria approximation algorithms were widely studied for degree constrained network design problems such as Bounded Degree MST and Bounded Degree Steiner Network, c.f. [31, 21, 20] and the references therein. A particular case of a bicriteria approximation is when only one parameter is relaxed while the cost/size of the solution is bounded by a budget $B$. For example, the $(1-1/e)$-approximation for the Budgeted Max-Coverage problem can be viewed as a bicriteria approximation $(1,1-1/e)$ for Set Cover, where only a fraction of $1-1/e$ of the elements is covered by $\mathrm{𝗈𝗉𝗍}$ sets. Similarly, in the budgeted version Budgeted ECSS of $k$-ECSS, instead of $k$ we are given a budget $B$ and seek a spanning subgraph of cost at most $B$ that has maximum edge-connectivity $k^{\ast }$.

One can view Theorem 1 as a $k^{\ast }-4$ additive approximation for Budgeted ECSS, where $k^{\ast }$ is the maximum edge-connectivity under the budget $B$. We note that budgeted connectivity problems were studied before for unit costs. Specifically, in the Min-Size $k$-ECSS and Min-Size $k$-CSS problems we seek a $k$-edge-connected and $k$-node-connected, respectively, spanning subgraph with a minimal number of edges. Nutov [24] showed that the following simple heuristic (previously analyzed by Cheriyan and Thurimella [1]) is a $(1,k-1)$ bicriteria approximation for Min-Size $k$-CSS: compute a min-size $(k-2)$-edge-cover $I_{k-2}$ (a spanning subgraph of minimal degree $\ge k-2$) and then augment it by an inclusion minimal edge set $F\subseteq E$ such that $I_{k-2}\cup F$ is $(k-1)$-connected. This $(1,k-1)$ bicriteria approximation implies a $k^{\ast }-1$ approximation for Budgeted Min-Size $k$-CSS, which is tight, since the problem is NP-hard. A similar result for $k$-ECSS, for large enough $k$, can be deduced from the work of Gabow and Gallagher [12].

One can obtain a bicriteria approximation $(2/\theta ,\lfloor k/\theta \rfloor )$ for $k$-ECSS for any $\theta \ge 1$, by just solving the $\lfloor k/\theta \rfloor$-ECSS problem. This is since the $2$ approximation is w.r.t. the Cut-LP. Specifically, if $x$ is a $k$-ECSS Cut-LP solution, then $x/\theta$ is a $\lfloor k/\theta \rfloor$-ECSS Cut-LP solution, thus a $2$-approximation w.r.t. Cut-LP for $\lfloor k/\theta \rfloor$-ECSS computes a $\lfloor k/\theta \rfloor$-connected subgraph of cost $\le 2/\theta \cdot {\mathrm{𝗈𝗉𝗍}}_k$. Similar “LP-scaling” gives a bicriteria approximation $(2/\theta ,\lfloor r_{uv}/\theta \rfloor )$ for any $\theta \ge 1$ for the Steiner Network problem.

The node connectivity version $k$-CSS of $k$-ECSS was also studied extensively [19, 6, 25, 1, 24, 2, 28, 26, 27]; it admits approximation ratio $4+ϵ$ when $k$ is bounded by a constant, but for general $k$ only a polylogarithmic approximation is known [6, 25]. The Survivable Network Design Problem (SNDP) is the node-connectivity version of Steiner Network when there should be $r_{uv}$ internally node disjoint path between every $u,v\in V$; $k$-CSS is a particular case when $r_{uv}=k$ for all $u,v\in V$. The Rooted SNDP is another particular case of SNDP where we require $k$ disjoint paths from a root $s$ to every node in a given set $T$ of terminals, and the $k$-Out-Connected Spanning Subgraph ($k$-OCSS) problem is a particular case of Rooted SNDP when $T=V\setminus \{s\}$. Since the best approximation ratios for these problems are w.r.t. to the Cut-LP (a.k.a. “biset LP”) they can be used to obtain bicretiria approximations using the method described above. We summarize the best approximation ratios for these problems and the bicriteria approximation ratios that can be derived for them by a simple “LP-scaling” in the following table.

This paper is organized as follows. In Sect. 2 we describe our iterative rounding algorithm. In Sect. 3 we prove the connectivity guarantee, and in Sect. 4 we prove a certain property of extreme point solutions that is used in the algorithm. Sect. 5 gives a bicriteria approximation $(3/2,k-2)$.

For an edge set $F$ and disjoint node sets $S,T$ let ${\delta }_F(S,T)$ denote the set of edges in $F$ with one end in $S$ and the other end in $T$, and let $d_F(S,T)=|{\delta }_F(S,T)|$. Let ${\delta }_F(S)={\delta }_F(S,\overline{S})$ and $d_F(S)=|{\delta }_F(S)|$, where $\overline{S}=V\setminus S$ is the node complement of $S$. For $x\in {ℝ}^E$ let $x(F)={\sum }_{e\in F}x(e)$. We will often refer to a proper subset $S$ of $V$ (so $\mathrm{\varnothing }\ne S\subset V$) as a cut. A standard Cut-LP for $k$-ECSS is:

As in HKZ [14], we will use the iterative rounding relaxation method. This means that while $E\ne \mathrm{\varnothing }$, we repeatedly compute an extreme point optimal solution $x$ to the Cut-LP above, and do at least one of the following steps:

1. 1.

   Remove from $E$ an edge $e$ with $x_e=0$.

2. 2.

   Add to a partial solution $I$ an edge $e$ with $x_e=1$, and remove $e$ from $E$.

3. 3.

   Relax some cut constraints $x(\delta (S))\ge k$ to $x(\delta (S))\ge k-q$ for some integer $q$.

The relaxation of the cut constraints will be implemented in two different ways.

1. (i)

   Relaxing the cut constraint of a single cut $S$ (and also of $\overline{S}=V\setminus S$) and then contracting $S$ into a single node $v_S$; this also removes the constraint of every cut $A$ such that both $A\cap S$ and $A\cap \overline{S}$ are non-empty. We will store the nodes that correspond to such relaxed contracted cuts $S$ in a set $U$.

2. (ii)

   Relaxing the constraints of all cuts $S$ that separate two nodes $u_1,u_2\in U$ (that correspond to contracted sets $C_1,C_2$) to $x(\delta (S))\ge k-2$. This is achieved by adding to the partial solution a “ghost edge” $u_1{u}_2$ of capacity $2$, and considering the “residual” demands of sets w.r.t the ghost edges. We will store the added ghost edges in a set $H$.

Instead of working with the cut constraints $x({\delta }_E(S))\ge k$ it would be convenient to consider the residual constraints $x({\delta }_E(S))\ge f(S)$ for an appropriately defined set function $f$. To define this $f$, suppose that we are already given:

• $\mathrm{■}$

  A partial solution $I$ of already chosen “integral” edges, that were removed from $E$.

• $\mathrm{■}$

  A set $H$ of “ghost-edges” – these are new virtual edges that are added to the solution.

• $\mathrm{■}$

  A set $U$ of nodes that correspond to contracted cuts whose constraints are relaxed.

Let $f(S)$ be a set function defined on proper node subsets $S$ by

This function $f(S)$ is a relaxation of the usual residual function $k-d_I(S)$ of $k$-ECSS. Consider the following LP-relaxation with the function $f$ above:

A set $S$ is $f$-positive if $f(S)>0$. Given an LP solution $x$ we say that $S$ is $x$-tight if the LP-inequality of $S$ holds with equality, namely, if $x(\delta (S))=f(S)$. An $x$-core, or simply a core if $x$ is clear from the context, is an inclusion-minimal $f$-positive $x$-tight set (note that an $x$-core must be $f$-positive and not only $x$-tight).

To contract a node subset $C$ of a graph $G=(V,E)$ means to identify all nodes in $C$ into one node $v_C$; edges that have an end in $C$ now have $v_C$ as their end and the arising loops (if any) are deleted. During the algorithm, we iteratively contract certain node subsets of $G$, so we denote the initial graph by $G_0=(V_0,E_0)$.

Our algorithm is given in Algorithm 1. The main difference between Algorithm 1 and that of HKZ is that we never add parallel ghost edges, namely we must have $d_H(u,v)=0$ whenever we add a ghost edge $uv$. This has a chain reaction of simplifying some other parts of the algorithm. For example, we add a ghost edge when $d_I(u,v)\ge \lceil (k-3)/2\rceil$ (and $d_H(u,v)=0$) while the analogous condition in HKZ is $d_{I\cup H}(uv)\in [k/2-2,k/2)$. The upper bound in HKZ is needed to control the number of parallel ghost edges added, which also complicates the analysis.

In Section 4 we will prove the following lemma about extreme point solutions of LP (2).

Interestingly, the two cases in Lemma 4 depend on whether there exist a laminar set family $ℒ$ such that $x$ is the unique solution to the equation system $\{x({\delta }_E(S)=f(S):S\in ℒ\}$. Specifically, if such $ℒ$ exists then case (i) in Lemma 4 holds, otherwise case (ii) must hold.

In the next Section 3 we will show that the algorithm terminates after a polynomial number of iterations and prove the connectivity guarantee $k-4$. Since in each iteration the cut constraints are only relaxed (by contractions, or by including nodes in $U$, or by adding ghost edges), the cost of the produced solution is at most the initial LP-value. In this context note that the $-2$ relaxation of the nodes $u,v\in U$ is not canceled when $u,v$ are removed from $U$, it is just replaced by the $-2$ relaxation caused by the added ghost edge $uv$.

For every ghost edge $h=uv$ added, let $I(h)=I(uv)$ be the set of (at least $\mu =\lceil (k-3)/2\rceil$) edges in $J$ that appear in ${\delta }_I(u,v)$. A key observation is the following.

Here we will prove Lemma 4. Fix an extreme point solution $x$ as in the Lemma. Then there exists a family $ℒ$ of $f$-positive $x$-tight sets such that $x$ is the unique solution to the equation system $\{x({\delta }_E(S))=f(S):S\in ℒ\}$; namely, $|ℒ|=|E|$ and the characteristic vectors of the sets $\{{\delta }_E(S):S\in ℒ\}$ are linearly independent. We will call such a family $ℒ$ $x$-defining. The following was essentially proved in [14].