Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this problem?
I'm aware that perfect matching has a formulation as a max-flow. One approach is, therefore, to find a min-cut in a corresponding graph, and see how many edges need to be removed so that the max-flow cannot carry as much flow. The problem with this approach is that a different min-cut might require the deletion of fewer edges, so it seems like this involves looking at all the min cuts in a graph.