Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n vertices on each part and with costs on its edges, k MOST VITAL EDGES ASSIGNMENT consists of determining a set of k edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, MIN EDGE BLOCKER ASSIGNMENT, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k MOST VITAL EDGES ASSIGNMENT is NP-hard to approximate within a factor c < 2 and MIN EDGE BLOCKER ASSIGNMENT is NP-hard to approximate within a factor 1.36. We also provide an exact algorithm for k MOST VITAL EDGES ASSIGNMENT that runs in O(n(k+2)). This algorithm can also be used to solve exactly MIN EDGE BLOCKER ASSIGNMENT. (C) 2013 Elsevier B.V. All rights reserved.