Given a bipartite graph, I need to find for each node, If this node exists in all the possible maximum matchings of the given graph or not.

Note that there can be multiple maximum matchings of a given bipartite graph with the same value of matching but different set of edges.

What is an efficient way to do this?

  • 2
    $\begingroup$ For a given node, you can remove the node and see whether this reduces the size of a maximum matching. There might be something more efficient in your case, though. $\endgroup$ – Yuval Filmus Apr 5 '17 at 15:51
  • $\begingroup$ I can tell you how to efficiently list all edges that are present in every maximum matching. I don't know how to efficiently list all vertices that are present in every maximum matching, though. Is that useful? If so, I can show the detailed explanation in an answer. It uses stackoverflow.com/q/41964288/781723 and stackoverflow.com/q/29418244/781723. (I'm hesitant to clutter up this page with an 'answer' that doesn't answer your question, for fear of causing the question to be treated as 'answered' when it really isn't.) $\endgroup$ – D.W. Apr 5 '17 at 17:37

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.