CODEWITHSUNDEEP
algorithmgraphmatchingbipartite
Sili
Sili

Reputation: 967

how to convert Bipartite Matching to Independent Set

I read the book Algorithm Design, chapter 1, it gave a very short description of how to convert Bipartite Matching to Independent Set Problem and I don't get it.

Do anybody know that any detailed matriel to describe this process? Thanks!

Upvotes: 4

Views: 2965

Answers (1)

Antti Huima
Antti Huima

Reputation: 25542

A maximum bipartite matching is a set of edges in a bipartite graph, no two edges being adjacent. A maximum independent set is a set of nodes (vertices) in a graph, no two vertices being adjacent.

So, you can convert a bipartite matching problem to independent set by converting every edge in your bipartite graph to a node, and then add an edge between all those newly created nodes that share a common endpoint in the original graph. Then a maximum independent set in the new graph corresponds to a maximum bipartite matching in the original problem.

Upvotes: 6

Related Questions