Improved Algorithms for MST and Metric-TSP Interdiction

André Linhares, Chaitanya Swamy

We consider the {\em MST-interdiction} problem: given a multigraph $G=(V,E)$, edge weights $\{w_e\ge 0{\}}_{e\in E}$, interdiction costs $\{c_e\ge 0{\}}_{e\in E}$, and an interd…