Interdiction of minimum spanning trees and other matroid bases

Noah Weninger, Ricardo Fukasawa

In the minimum spanning tree (MST) interdiction problem, we are given a graph $G=(V,E)$ with edge weights, and want to find some $X\subseteq E$ satisfying a knapsack constraint suc…