Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M <Superscript>0</Superscript>, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M <Superscript>0</Superscript> can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n <Superscript>3</Superscript>). Copyright Springer Science+Business Media, LLC. 2013