how to convert Bipartite Matching to Independent Set

Question

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!

Answer 1

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.