# How to cover given entries in a matrix with minimum number of rows and columns?

We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.

example

0 0 1 0

0 1 0 1

0 0 1 0

0 0 1 0

cover 3rd column and 2nd raw. so two plates.

## 1 Answer

Let $$R=\{r_1, \cdots, r_n\}$$ be the set of all rows. Let $$C=\{c_1, \cdots, c_m\}$$ be the set of all columns. If and only if the matrix entry at row $$i$$ and column $$j$$ is 1, we connect $$r_i$$ with $$c_j$$ with an edge. Now we have a bipartite graph $$G=((R,C), V)$$, since there is no edge between two rows nor between two columns.

A vertex cover of $$G$$ corresponds to a set of selected rows and columns such that each matrix entry of 1 is in at least one of selected rows or columns. So, the problem to find minimum number of covering plates is the same as determining the minimum vertex cover for graph $$G$$.

Thanks to Kőnig's theorem, for bipartite graph $$G$$, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. So, the problem is shifted to find a a maximum-cardinality matching of $$G$$.

There are many efficient algorithms that finds a maximum-cardinality matching in a bipartite graph, such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. There are many existing implementations of them in various programming languages that can be easily searched.