期刊
DISCRETE APPLIED MATHEMATICS
卷 158, 期 15, 页码 1676-1690出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2010.06.006
关键词
Maximum matching; Interdiction; Complexity; Approximation algorithm; Bounded treewidth
We introduce two interdiction problems involving matchings, one dealing with edge removals and the other dealing with vertex removals. Given is an undirected graph G with positive weights on its edges. In the edge interdiction problem, every edge of G has a positive cost and the task is to remove a subset of the edges constrained to a given budget, such that the weight of a maximum matching in the resulting graph is minimized. The vertex interdiction problem is analogous to the edge interdiction problem, with the difference that vertices instead of edges are removed. Hardness results are presented for both problems under various restrictions on the weights, interdiction costs and graph classes. Furthermore, we study the approximability of the edge and vertex interdiction problem on different graph classes. Several approximation-hardness results are presented as well as two constant-factor approximations, one of them based on iterative rounding. A pseudo-polynomial algorithm for solving the edge interdiction problem on graphs with bounded treewidth is proposed which can easily be adapted to the vertex interdiction problem. The algorithm presents a general framework to apply dynamic programming for solving a large class of min-max problems in graphs with bounded treewidth. Additionally, we present a method to transform pseudo-polynomial algorithms for the edge interdiction problem into fully polynomial approximation schemes, using a scaling and rounding technique. (C) 2010 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据