On the inverse maximum perfect matching problem under the bottleneck-type Hamming distance

Abstract

Given an undirected network G(V,A,c) and a perfect matching M of G, the inverse maximum perfect matching problem consists of modifying minimally the elements of c so that M becomes a maximum perfect matching with respect to the modified vector. In this article, we consider the inverse problem when the modifications are measured by the weighted bottleneck-type Hamming distance. We propose an algorithm based on the binary search technique for solving the problem. Our proposed algorithm has a better time complexity than the one presented in cite{Liu}. We also study the inverse assignment problem as a special case of the inverse maximum perfect matching problem in which the network is bipartite and present an efficient algorithm for solving the problem. Finally, we compare the algorithm with those presented in the literature.