8
$\begingroup$

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.

$\endgroup$
2
  • 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$ Commented Jan 23, 2018 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$
    – Wei Zhan
    Commented Feb 9, 2018 at 20:45

1 Answer 1

1
$\begingroup$

This problem is known as the preclusion number of a graph, or minimum blocker perfect matching problem. It was shown to be $\mathcal{NP}$-hard in Lacroix, Mathieu; Mahjoub, A. Ridha; Martin, Sébastien; Picouleau, Christophe, On the NP-completeness of the perfect matching free subgraph problem, Theor. Comput. Sci. 423, 25-29 (2012). ZBL1237.68089.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.