A set E' of k edges in a multigraph G=(V,E) is said to be a k most vital edge set (k-MVE set) if these edges being removed from G, the resultant graph G'=(V,E-E') has minimum number of spanning trees. The problem of finding a k-MVE set for two-terminal series-parallel graphs is considered in this paper. The authors present an O(ℝEℝ) time algorithm for the case k=1, and an O(ℝVℝk+ℝEℝ) time algorithm for arbitrary k.
