 |
Center for Nonlinear Studies |
In the matching interdiction problem, one is given a budget and a weighted graph with nonnegative integer edge costs and edge weights. The optimizer needs to find a set of edges with total cost less than the allocated budget such that when the edges are deleted, the weight of the maximum matching in the remaining graph is minimized. In this presentation, we introduce a pseudo-polynomial time approximation scheme for the matching interdiction problem on planar graphs. This algorithm extends Baker's technique to interdiction problems, building off of Zenklusen's work on pseudo-polynomial algorithms for interdiction problems on graphs with bounded treewidth. We also present approximation-preserving and local bounded treewidth-preserving reductions from the interdiction versions of the undirected shortest path, directed shortest path, minimum cut, and minimum spanning tree problems to the minimum perfect matching interdiction problem, which we introduce. This work has potential practical applications in border security and infrastructure network maintenance.
Host: Feng Pan