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
    Is there any hope that a greedy algorithm would work? (At each stage pick an index $i$ such that the number of $1$s in row $i$ and column $i$ is largest possible.)2012-06-27
  • 0
    @ArthurFischer Nope. Just consider the matrix $0 1 1 1 \\ 1 1 0 0 \\ 1 0 1 0 \\ 1 0 0 1$. What is left is the $0$ on the (1,1) position, yet a greedy algorithm eliminates the first row first.2012-06-27
  • 0
    @N.S. Thanks. I knew it couldn't be that simple, but I couldn't think of a good reason.2012-06-27
  • 0
    This seems more a graph theory question: Consider the directed graph for which this is the corresponding matrix. You need to erase some vertices and all edges incident to those edges in order to get the largest possible null graph...2012-06-27
  • 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).

  • 0
    Thank you , i will check it out. sry cannt upvote due to my low rep.2012-06-27
  • 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
    i have edited : the diagonals are always 0 in my case.2012-06-27
  • 0
    Is it correct way to find frequency of 1's for specific nos and proceed in decreasing order?2012-06-27
  • 0
    @JCH: that way doesn't always find the fastest method (see comments on your question).2012-06-27
  • 0
    Thank you for your suggestion.2012-06-27