An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees (Q1821118)

Given a digraph G(V,E) the problem under study, called k-vertex- connectivity unweighted augmentation problem, is to find the smallest possible set E'\(\subset V\times V\) such that G'(V,E\(\cup E')\) is k- vertex-connected. The paper presents a survey of the known results concerning an algorithmical complexity of the problem for different types of graphs and different k. Then, the attention is focused on solving the problem for rooted directed trees. For this special case an algorithm is presented enabling to solve the problem in O(k\(| V|)\) time. Moreover, it is shown that the algorithm is optimal except for a constant factor.