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.

  • 2
    $\begingroup$ The obvious min-cut in the flow formulation cuts every edge in the bipartite graph (and none of the additional ones from the source and to the sink), so it is not very promising at all. If the graph is not sparse (i.e. $E = \omega(V)$) then the vertex with lowest order gives an upper bound on the number of edges to delete, and searching subsets of $E$ which are smaller than that is $o(2^E)$ and hence asymptotically better than the naïvest approach. $\endgroup$ – Peter Taylor Jan 23 '18 at 14:45
  • $\begingroup$ @PeterTaylor The min-cut corresponding to the maximum matching of a bipartite graph is definitely NOT the one cutting every edge. Its weight is even larger than the weight of the matching. $\endgroup$ – Willard Zhan Feb 9 '18 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.