Directed vertex-connectivity augmentation

The problem of finding a smallest set of new edges to be added to a given directed graph to make it k-vertex-connected was shown to be polynomially solvable recently for any target connectivity k ≥ 1. However, the algorithm given there relied on the ellipsoid method. Here we refine some results which makes it possible to construct a combinatorial algorithm which is polynomial for any fixed k. Short proofs for (extensions of) some earlier results related to this problem will also be given.