# S-T edge-connectivity augmentation

Given a digraph *D=(V,A)*, two (not necessarily disjoint) subsets [math]S,T\subseteq V[/math] and
a connectivity requirement *k*, develop a strongly polynomial time combinatorial algorithm for finding a minimum cardinality arc-set whose addition makes *D* *k*-edge-connected between *S* and *T*, that is, it contains *k* edge-disjoint paths from any node in *S* to any node in *T*.

## Remarks

A min-max formula for the optimum value follows from the Frank-Jordán theorem. Along with the theorem, Frank and Jordán gave an algorithm based on the ellipsoid method, which is neither combinatorial nor strongly polynomial. Benczúr and Végh^{[1]} developed a pseudopolynomial combinatorial algorithm, that is, the running time is a function of the maximum value of the requirement function.

Note that in our case, in contrast to the node-connectivity augmentation problem, *k* may be arbitrarily large, irrespectively of the size of *V*. To ensure that the output size is polynomial, the augmenting arc set may be represented as a vector [math]V\times V\rightarrow \mathbb{Z}_+[/math].

For an edge-weighted digraph, it is NP-hard to find a minimum weight sub-digraph that is *k*-edge-connected between *S* and *T*. An approximation algorithm for this problem is presented in ^{[2]}.

## References

- ↑ L. A. Végh, A. A. Benczúr,
*Primal-dual approach for directed vertex connectivity augmentation and generalizations*, DOI link, Author link - ↑ J. Cheriyan, B. Laekhanukit,
*Approximation Algorithms for Minimum-Cost k-(S,T) Connected Digraphs*, DOI link, author link