B-Matching Interdiction Problem on Undirected Trees

Abstract

In this paper, we consider a network optimization interdiction problem, called the [Formula: see text]-matching interdiction problem on undirected trees with unit edge weights. Given an undirected tree [Formula: see text], each vertex [Formula: see text] has a capacity [Formula: see text], the [Formula: see text]-matching of [Formula: see text] is an edge subset [Formula: see text] such that the number of edges in [Formula: see text] incident to [Formula: see text] is at most [Formula: see text] for each [Formula: see text]. A maximum [Formula: see text]-matching is a [Formula: see text]-matching that contains the largest number of edges among all possible [Formula: see text]-matchings. In this paper, we consider two problems: (1) The [Formula: see text]-matching edge interdiction problem. Each edge of [Formula: see text] has an interdiction cost. Each vertex of [Formula: see text] has a capacity. There is also an interdiction budget. The goal is to remove a subset of the edges constrained to a budget such that the size of maximum [Formula: see text]-matching in the resulting graph is minimized. (2) The [Formula: see text]-matching vertex interdiction problem. Each vertex of [Formula: see text] has an interdiction cost and a capacity. There is also an interdiction budget. The goal is to remove a subset of the vertices constrained to a budget such that the size of maximum [Formula: see text]-matching in the resulting graph is minimized. We first show that both problems are NP-hard. Then, we propose several pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for both problems.