7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Shouldn't it be (m + n) x 2m? $\endgroup$ – antti.huima Jul 2 '13 at 16:35
  • 1
    $\begingroup$ You probably want to say that this is a reduction from SAT. $\endgroup$ – András Salamon Jul 2 '13 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$ – Marzio De Biasi Jul 2 '13 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$ – antti.huima Jul 2 '13 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 '13 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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