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.


2 Answers 2


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.

  • $\begingroup$ Shouldn't it be (m + n) x 2m? $\endgroup$ Jul 2, 2013 at 16:35
  • 1
    $\begingroup$ You probably want to say that this is a reduction from SAT. $\endgroup$ Jul 2, 2013 at 16:35
  • $\begingroup$ Why do you say that the first $n$ rows forces to choose $x_i$ or $\neg x_i$? One can choose both. $\endgroup$ Jul 2, 2013 at 16:37
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 2, 2013 at 16:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis
    Jul 2, 2013 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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