Fast reoptimization for the minimum spanning tree problem

We study reoptimization versions of the minimum spanning tree problem. The reoptimization setting can generally be formulated as follows: given an instance of the problem for which we already know some optimal solution, and given some “small” perturbations on this instance, is it possible to compute a new (optimal or at least near-optimal) solution for the modified instance without ex nihilo computation? We focus on two kinds of modifications: node-insertions and node-deletions. When k   new nodes are inserted together with their incident edges, we mainly propose a fast strategy with complexity O(kn)O(kn) which provides a max{2,3−(2/(k−1))}max{2,3−(2/(k−1))}-approximation ratio, in complete metric graphs and another one that is optimal with complexity O(nlogn). On the other hand, when k   nodes are deleted, we devise a strategy which in O(n)O(n) achieves approximation ratio bounded above by 2⌈|Lmax|/2⌉2⌈|Lmax|/2⌉ in complete metric graphs, where LmaxLmax is the longest deleted path and |Lmax||Lmax| is the number of its edges. For any of the approximation strategies, we also provide lower bounds on their approximation ratios.