# maximum bipartite matching

I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that ﬁnds a maximum-sized subset of the rooks such that if we leave this subset on the chessboard and remove all other rooks, then no two rooks attack one another. (Two rooks are said to attack one another if and only if they are either in the same row or in the same column with no other intervening rooks between them.)

My idea for solving this problem is to consider a bipartite graph (X,Y) where X is the rows in the chessboard and Y is the columns. if a row and column have a rook placed at their intersection, then there is an edge between the those vertices from x to y. This can be converted into a maximum flow network and the value of max flow is the max matching.

In order to find a polynomial time algorithm i can run maybe BFS.

I wanted to know that if i build my solution on this idea shall it be correct. Is there a better algorithm (polynomial in m and n)?

Any help is appreciated.

• When i convert the maximum bipartite graph to a flow network, the edges are directed and weighted. All the edges are assigned capacities 1, also source and sink are added and edge between source s and x has capacity infinite. So it would be a directed weighted graph at the end, and i have to find the maximum flow in the netwrok. Mar 20, 2014 at 16:26