Efficient determination of the k most vital edges for the minimum spanning tree problem

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit enumeration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.

► k most vital edges for minimum spanning tree. ► The best explicit enumeration algorithm for general k and second best for fixed k. ► It can be adapted into a practically efficient implicit enumeration algorithm. ► A very efficient approximation algorithm providing solutions of guaranteed quality. ► An integer programming formulation is given, but shown to be much less efficient.