The Matching Interdiction Problem in some Special Classes of Graphs

Abstract

This paper is based on two main concepts: the matching and interdiction. Consider the graph  that each edge has a positive weight. The purpose of the matching interdiction problem in the weighted graph G with the weight v(G) is to delete a subset of vertices, denoted by R^*, such that the weight of the maximum matching in the resulted graph is minimized. We first restrict this problem to the case of deleting two vertices of the in graph. Then, we compute the quantity  〖(v(G)-v(G[V\R^*]))〗∕〖(v(G)-v(G[V\R]))〗  some special classes of graphs, where v(G[V\R^*]) and  v(G[V\R]) are the weights of the maximum matching in the graphs G[V\R^*] and G[V\R], respectively. We show that the limit of this proportion in some sequences of graphs tends to its maximum value. We prove that the limit of this proportion can be decreased in the sequence of the wheel graphs. Also, if the weight of all edges in the complete graph is equal, the approximate and optimal solutions will be the same. At end, we generalize the results related to the path graph when the purpose is to delete B even vertices.