Let $G$ be a bipartite graph with vertex set $V=V_1 \cup V_2$. If $\mid V_1\mid= n$ and $\mid V_2\mid=m$ with $m\leq n$, then how to find all minimal vertex cover?

  • $\begingroup$ Minimal vertex covers can be computed easily from maximal matchings (for bipartite graphs). This paper gives a method to enumerate all maximal matchings. $\endgroup$ – Mike Earnest May 16 at 16:41
  • $\begingroup$ Thank you so much for the paper. $\endgroup$ – Martia May 18 at 2:19

This is largely dependent from bipartite graph to bipartite graph, Konig's Theorem states that the size of the minimal vertex cover is the size of the maximal matching. In your case, the largest matching can be at most $m$. Also see Hall's Theorem.

  • $\begingroup$ Thank you for your help. $\endgroup$ – Martia May 18 at 2:20

Your Answer

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

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