The Constrained Arborescence Augmentation Problem in Digraphs

The augmentation problem originally determines a minimum weight arc-set that is added to an original network to satisfy a given property. In the real communication network, continuous transmission may lead some transmission lines of this original network to be damaged such that communication network cannot be used. The problem that we consider is how to add other transmission lines to construct a more survivable communication network to service well. In details, we consider the constrained arborescence augmentation problem (CAA, for short) as follows. For a given weighted digraph (or network) D = (V, A; w; T-r) where w : A -> R+ is a weighted function and T-r = (V, A(r)) is an arborescence rooted at r in D, we are asked to find an arc-subset A' from A - A(r) such that there exists still an arborescence in the new digraph D' = (V, A(r) boolean OR A' - {a}) for each arc a is an element of A(r), the objective is to, minimize the total weight w(A') = Sigma(e is an element of A') w(e). In this paper, we prove that the CAA problem still remains NP-hard, whose proof follows from a reduction from the 3-dimensional matching. In addition, we present an optimal O(m + n log n) combinatorial algorithm in time to solve this problem for special version where an arborescence in digraph D' = (V, A(r) boolean OR A' - {a}) still has its fixed root r, for each arc a is an element of A(r.)