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
