# Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no row containing only zeroes, in other words, every row contains at least one $1$?

For example, given the $4 \times 3$ matrix

$\begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{bmatrix}$

a subset of $k=3$ columns that fails to fulfill this condition is that of the first columns, as the third row has all zeros within this submatrix, but the column set $\{1, 3, 4\}$ would be a solution.

I suspect this is a hard problem, but I haven't been able to find a direct reference. I'm interested in this problem because of its applications in cryptography.

Rephrasing as a set system, each row represents a subset $E_i$ of some set $X$, for $i=1,2,\dots,m$. You want a set $Y \subseteq X$ with at most $k$ elements, such that $E_i \cap Y \ne \emptyset$ for each $i$. In other words, you want a hitting set of size at most $k$; this problem is NP-complete.

It is NP-hard, here is a reduction from SAT:

You have variables $x_1,\dots,x_m$, and clauses $C_1,\dots,C_n$ on these variables.

You build the following $(m+n)\times 2m$ matrix:

For $i\in[1,m]$, the $i^{th}$ row contains only $0$ except two $1$'s in column $i$ (representing variable $x_i$) and column $m+i$ (representing $\neg x_i$).

Then, the following $n$ rows are clauses : row $n+j$ contains exactly variables (or negated variables) appearing in clause $C_j$.

There exists a subseteq of columns of size $m$ if and only if the formula is satisfiable. The first $m$ rows forces to choose for each $i$, either $x_i$ or $\neg x_i$, and the last rows ensures that every clause is satisfied by the chosen valuation.

• Shouldn't it be (m + n) x 2m? – antti.huima Jul 2 '13 at 16:35
• You probably want to say that this is a reduction from SAT. – András Salamon Jul 2 '13 at 16:35
• Why do you say that the first $n$ rows forces to choose $x_i$ or $\neg x_i$? One can choose both. – Marzio De Biasi Jul 2 '13 at 16:37
• There is something wrong with the argument, because you could indeed pick for the first $i < m/2$ variables both $x_i$ and $\neg x_i$ and if every clause contains one of those variables then you have a solution. That is, you make some form of an assumption about the structure of the clauses that is not apparent in the text. – antti.huima Jul 2 '13 at 16:45
• Your counter-example does not work because the matrix contains lines forcing you to choose $x_2$ or $\neg x_2$, and $x_3$ or $\neg x_3$. This is not forced by the clauses, but by the first $m$ lines. – Denis Jul 2 '13 at 16:57