Can this algorithm on removing $1$'s from a $(0,1)$-matrix fail?

Question

Let us be given a $n\times n$ matrix containing only zeros and ones.Now, the goal is to remove some 'ones' from the matrix (i.e. replace them with zeros) so that in each row and each column there is at most one 'one'. Of course, it is preferable that we leave as much 'ones' as it is possible (maximum is obviously $n$).

Now, let us define the following algorithm: if there is a 'one' which is all alone in a column or a row, leave it there, and replace all 'ones' in its column and row with zeros. We repeat the process as long as there are single 'ones' in rows or columns. If there are no single 'ones' left, we take the first row or column (first is counted from up (for rows) and from left (for columns)) containing two 'ones' (if there are no pairs, we go for the first triplet and so on). In that pair (or triplet, or ...) we leave the first 'one' intact (first is counted from the left for elements of row, from the top for elements of a column) and change all other 'ones' in the row and column of that first 'one' into zeros. Now, we check are there now any single 'ones' as defined above - if yes, we repeat that part of the algorithm, if no, we look for the first pair, triplet, etc. The algorithm ends when all 'ones' are singles both in their column and row.

Does this algorithm always give the maximum covering, i.e. does it always terminate with maximal number of 'ones' in the final matrix? In other words, can there be a matrix with a possible exclusion of some ones such that it ends up with $n$ ones using some other exclusion scheme, while ending up with less than $n$ 'ones' using the algorithm described above?

Answer 1

Yes. Consider a large square matrix with two large square blocks filled with ones and one empty row and one empty column. Delete one one from each of the blocks off the diagonal, and place a corresponding one in the empty row and column. You now have one row with two elements, the rest having many elements, and one column having only two elements, the rest having many. Your procedure will deal with the sparesely populated row and column first. Permute the rows and columns so that you procedure links the two choices with different blocks. Now the remainder of each block has one more row than it has columns or vice versa, as a perfect matching cannot exist. It is easy to see however that a perfect matching existed before your algorithm matched the sparse row and column.

Answer 2

I'm not sure about whether this works, but I'd be doubtful.

Another way to express this problem is finding maximum partial matchings in a bipartite graph. (Just interpret the matrix an adjacency matrix for the graph). By a maximum partial matching I mean a maximal-sized set of edges no two having a vertex in common.

The reason for my scepticism is that if your algorithm worked, then it would give an algorithm for finding the solution in the situation of Hall's marriage theorem. Your algorithm is "monotone" in the sense that it adds edges but never removes them, but all the algorithms I have seen for Hall's theorem, one needs to remove edges in certain circumstances in the process.

For the problem is hand, an algorithm comes from any that solves the maximum flow problem in a network. Attach a source to each vertex on one side of the bipartition and a sink to each vertex on the other side. Give all edges unit capacity and find a maximum flow.

Answer 3

Diagram to give an example for deinst's answer. I tried putting this in a comment, but it stuffed up the formatting. The Xs marks ones that give a complete match

X01100001
1X1100000
11X100000
111X00000
00001011X
0000X1110
000011X10
0000111X0
01000X000

Now, suppose we take the two squares marked by Y's

*0**0000Y
111100000
111100000
111100000
00001011*
00001*110
00001*110
00001*110
0*000Y000

We have two 3 by 4 squares left, so we can take 6 more items. This give a total of 8 instead of 9. We can enforce those two blocks to be taken by using a permutation.

Answer 4

Yes. Consider a large square matrix with two large square blocks filled with ones and one empty row and one empty column. Delete one one from each of the blocks off the diagonal, and place a corresponding one in the empty row and column. You now have one row with two elements, the rest having many elements, and one column having only two elements, the rest having many. Your procedure will deal with the sparesely populated row and column first. Permute the rows and columns so that you procedure links the two choices with different blocks. Now the remainder of each block has one more row than it has columns or vice versa, as a perfect matching cannot exist. It is easy to see however that a perfect matching existed before your algorithm matched the sparse row and column.

Answer 5

I'm not sure about whether this works, but I'd be doubtful.

Another way to express this problem is finding maximum partial matchings in a bipartite graph. (Just interpret the matrix an adjacency matrix for the graph). By a maximum partial matching I mean a maximal-sized set of edges no two having a vertex in common.

The reason for my scepticism is that if your algorithm worked, then it would give an algorithm for finding the solution in the situation of Hall's marriage theorem. Your algorithm is "monotone" in the sense that it adds edges but never removes them, but all the algorithms I have seen for Hall's theorem, one needs to remove edges in certain circumstances in the process.

For the problem is hand, an algorithm comes from any that solves the maximum flow problem in a network. Attach a source to each vertex on one side of the bipartition and a sink to each vertex on the other side. Give all edges unit capacity and find a maximum flow.

Answer 6

Diagram to give an example for deinst's answer. I tried putting this in a comment, but it stuffed up the formatting. The Xs marks ones that give a complete match

X01100001
1X1100000
11X100000
111X00000
00001011X
0000X1110
000011X10
0000111X0
01000X000

Now, suppose we take the two squares marked by Y's

*0**0000Y
111100000
111100000
111100000
00001011*
00001*110
00001*110
00001*110
0*000Y000

We have two 3 by 4 squares left, so we can take 6 more items. This give a total of 8 instead of 9. We can enforce those two blocks to be taken by using a permutation.