Edge-connectivity augmentation preserving simplicity

Given a simple graph G=(V, E), the goal is to find a smallest set F of new edges such that G=(V, E∪F) is κ edge connected and simple. Very recently this problem was shown to be NP hard by T. Jordan (1997). We prove that if OPT_P^κ is high enough-depending on κ only-then OPT_S^κ=OPT_P^κ holds, where OPT_S^κ (OPT_P^κ) is the size of an optimal solution of the augmentation problem with (without) the simplicity preserving requirement, respectively. Furthermore, OPT_S^κ-OPT_P^κ ⩽g(κ) holds for a certain (quadratic) function of κ. Based on these results an algorithm is given which computes an optimal solution in time O(n⁴) for any fixed κ. Most of these results are extended to the case of non-uniform demands, as well