Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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.) –  Arthur Fischer Jun 27 '12 at 16:48
    
@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. –  N. S. Jun 27 '12 at 16:56
    
@N.S. Thanks. I knew it couldn't be that simple, but I couldn't think of a good reason. –  Arthur Fischer Jun 27 '12 at 16:57
    
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... –  N. S. Jun 27 '12 at 17:06
    
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 student.dtu.dk/~s082951/01227/01227-GraphTheory.pdf –  utdiscant Jun 27 '12 at 18:28
add comment

2 Answers

up vote 1 down vote accepted

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).

share|improve this answer
    
Thank you , i will check it out. sry cannt upvote due to my low rep. –  JCH Jun 27 '12 at 18:36
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. –  utdiscant Jun 27 '12 at 18:37
add comment

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.

share|improve this answer
    
i have edited : the diagonals are always 0 in my case. –  JCH Jun 27 '12 at 17:04
    
Is it correct way to find frequency of 1's for specific nos and proceed in decreasing order? –  JCH Jun 27 '12 at 17:07
    
@JCH: that way doesn't always find the fastest method (see comments on your question). –  Ben Millwood Jun 27 '12 at 17:29
    
Thank you for your suggestion. –  JCH Jun 27 '12 at 18:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.