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$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$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$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.