Binary matrix column subset selection complexity

Question

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.

Answer 1

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.

Answer 2

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.