Need pointer to an algorithm - might be a spanning tree, not sure

[groston]

I am trying to solve a problem for which, I am certain, a solution already exists, but I have not been able to track it down. Even just knowing the proper name would help immensely.

Here is the problem: Consider the following matrix (as an example)

1 1 1 0 0 0
1 1 1 0 1 1
1 1 1 0 1 1
0 0 1 0 0 1
0 0 1 0 0 0
1 0 0 1 1 1
1 0 0 1 0 0
0 0 0 0 1 1
1 1 0 1 1 0

What I would like is an algorithm which will return the minimum set of columns such that the set of columns has a one in each row. If there are multiple such sets, all should be returned. Thus, for this example, the answer (I think) would be {1,3,5} and {1,3,6}. For the application in mind, the size of the matrix will be relatively small, probably not more than a one or two dozen columns and one hundred rows (i.e., even if the problem is technically NP hard (which I doubt), the size is small enough that it can be solved in a reasonable period of time.)

My first thought was that the answer was related to the column rank, but that is not at all correct. This has some elements of a spanning tree, but that also doe snot seem to be correct.

Thanks for your help.

 

[daon2]

Sorry, I missread. I'm still not sure what you are asking. But no columns have a 1 in each row?

 

[groston]

Correct - in the example shown, no single column has a one in all rows. However, there are multiple sets of columns which taken together do have at least one one in each row. What I am seeking is the set(s) with the fewest number of columns such that there is a one in each row.