  In the matching interdiction problem, we are given an undirected graph with
weights and interdiction costs on the edges and seek to remove a subset of the
edges constrained to some budget, such that the weight of a maximum weight
matching in the remaining graph is minimized. In this work we introduce the
matching interdiction problem and show that it is strongly NP-complete even
when the input is restricted to simple, bipartite graphs with unit edge weights
and unit interdiction costs. Furthermore, we present a pseudo-polynomial
algorithm for solving the matching interdiction problem on graphs with bounded
treewidth. The proposed algorithm extends the approach that is typically used
for the creation of efficient algorithms on graphs with bounded treewidth to
interdiction problems.
