EDGE-CONNECTIVITY AUGMENTATION PRESERVING SIMPLICITY

Given a simple graph G = (V, E), our goal is to find a smallest set F of new edges such that G = (V, E boolean OR F) is k-edge-connected and simple. Recently this problem was shown to be NP-complete. In this pa per we prove that if OPTPk is high enough-depending on k only-then OPT Sk = OPTPk holds, where OPTSk (OPTPk) is the size of an optimal soluti on of the augmentation problem with (without) the simplicity-preservin g requirement, respectively. Furthermore, OPTSk - OPTPk less than or e qual to g(k) holds for a certain (quadratic) function of k. Based on t hese facts an algorithm is given which computes an optimal solution in time O(n(4)) for any fixed k. Some of these results are extended to t he case of nonuniform demands as well.