3
$\begingroup$

I have a $5 \times 5$ grid as below $\begin{array}{ccccc} 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 0 \end{array}$

It can be safely assumed the diagonals are always 0.

Now the problem is to eliminate the 1's in the grid above by choosing minimum numbers (1 to 5) such that if we strike of that numbered row and columns both then only zeros remain. example for above matrix if we choose 1,4: strike off all cells row 1 and column 1 strike off all cells row 4 and column 4 Now only 0's remain.

So the problem is to find a fast way choose minimum such numbers so that all 1's strike out.

Please suggest a way forward as I am stuck and cannot find correct way.

The Grid Dimension $N$ : $1\leq N\leq 100$.

Many thanks for your help.

Edit: My bad, It can be safely assumed the diagonals are always 0.

  • 0
    This corresponds to finding a minimal covering in a bipartite graph. The problem is not hard. Look at Section 6.3.2 and Section 6.2 here http://www.student.dtu.dk/~s082951/01227/01227-GraphTheory.pdf2012-06-27

2 Answers 2

1

If you are allowed to cross out rows and columns independently, the problem corresponds to finding a minimum covering in a bipartite graph. This means that you for example are allowed to cross out column 1 and 2, while not crossing out rows 1 and 2.

In general, finding minimum coverings is a hard problem, but in bipartite graphs, the problem can be solved in polynomial time.

Given such a matrix, you can look at it as a biadjacency matrix. Now you need to find a minimum covering in this bipartite graph (a minimum set $S$ of vertices, such that a removal of the vertices in $S$ removes all edges), corresponding to a minimum set of rows and columns in the matrix, such that those rows and columns contain all the ones.

This is also known as the structure rank of the matrix, and you can read more about this in these lecture notes. Section 6.2 describes an algorithm for finding such a minimum covering in a bipartite graph (using the Hungarian Algorithm for finding a maximum matching), and Section 6.3.2 describes exactly the matrix-problem you are considering (the problem of finding the structure rank of a matrix).

  • 1
    If you have some questions regarding the method, just ask in a comment, and I will try to extend the answer in the right way.2012-06-27
1

A short comment, which simplifies a little the problem. If any diagonal element $a_{ii}=1$, then it has to be eliminated by picking the number $i$ (no other choice)...

You can start by picking all i so that $a_{ii}=1$, and eliminate then, obtaining a smaller matrix and an equivalent problem.

After that the problem is basically the following: Cosider a matrix without 1's on the diagonal, and let $S:= \{ (i,j)|a_{ij}=1 \}$. Find the smallest T so that

$S \subset (T \times \{ 1,2,..., N\}) \cup ( \{ 1,2,..., N\} \times T) $

Edited, a new idea

Draw a simple graph the following way: $V= \{ 1, 2, 3,...n \}$ and put an edge between $i$ and $j$ if and only if $i\neq i$ and $a_{ij}=a_{ji}=0$.

Then I think the problem becomes equivalent to finding the max clique for this graph. There are no polynomial time algorithms for this problem, but it is a well known and studied problem, there might be some algorithms around.

Note that if your original matrix is symmetric, the two problems seem equivalent. This suggest that there is no known "very fast" algorithm for this problem.

  • 0
    Thank you for your suggestion.2012-06-27