<p>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 <a href="http://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation">hitting set</a> of size at most $k$; this problem is NP-complete.</p>

CC BY-SA 3.0
2013-07-02T16:33:02.490Z
2013-07-02T16:33:02.490Z
András Salamon
<p>It is NP-hard, here is a reduction from SAT:</p>

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

<p>You build the following $(m+n)\times 2m$ matrix:</p>

<p>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$).</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-07-02T16:35:24.360Z
Shouldn't it be (m + n) x 2m?
antti.huima
CC BY-SA 3.0
2013-07-02T16:35:45.610Z
You probably want to say that this is a reduction _from_ SAT.
András Salamon
CC BY-SA 3.0
2013-07-02T16:37:20.150Z
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
CC BY-SA 3.0
2013-07-02T16:41:51.853Z
because your subset of columns has to pick a $1$ in line $i$, and the only ones are those corresponding to $x_i$ and $\neg x_i$, meaning you have to pick one of the two. You cannot pick both, because you are allowed only $m$ columns in total, so it is just enough to choose a valuation. If you choose both, there will be a $j$ such that neither $x_j$ nor $\neg x_j$ is in your subset.
Denis
CC BY-SA 3.0
2013-07-02T16:44:49.543Z
What about: $x_1 \land \neg x_1 \land (x_2 \lor x_3)$? $m = 3$ but one can pick columns $x_1, \neg x_1, x_2$ and make the formula satisfiable. But perhaps I didn't understand well your reduction.
Marzio De Biasi
CC BY-SA 3.0
2013-07-02T16:45:22.177Z
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
CC BY-SA 3.0
2013-07-02T16:57:01.520Z
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
CC BY-SA 3.0
2013-07-02T19:25:14.783Z
@dkuper: ok, I understood it.
Marzio De Biasi
CC BY-SA 3.0
2013-07-02T16:26:23.213Z
2018-02-28T11:50:58.247Z
2018-02-28T11:50:58.247Z
Denis
<p>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$?</p>

<p>For example, given the $4 \times 3$ matrix</p>

<p>$\begin{bmatrix} 1 &amp; 0 &amp; 0 &amp; 1 \\
                 0 &amp; 1 &amp; 1 &amp; 0 \\
                 0 &amp; 0 &amp; 0 &amp; 1 \\
                 1 &amp; 1 &amp; 0 &amp; 1 \end{bmatrix}$</p>

<p>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.</p>

<p>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.</p>

<np-hardness><combinatorics><boolean-matrix>
Binary matrix column subset selection complexity
antti.huima
# Binary matrix column subset selection complexity

(Asked by: username_0 on 2013-07-02)

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.

**Tags:** np-hardness, combinatorics, boolean-matrix


---

## 2 answers

### Answer by username_1 on 2013-07-02. Score: 8 | Accepted answer

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](http://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation) of size at most $k$; this problem is NP-complete.


---

### Answer by username_2 on 2013-07-02. Score: 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.

> **Comments:**
> **username_0**: Shouldn't it be (m + n) x 2m?  
> **username_1**: You probably want to say that this is a reduction _from_ SAT.  
> **username_3**: Why do you say that the first $n$ rows forces to choose $x_i$ or $\neg x_i$? One can choose both.  
> **username_2**: because your subset of columns has to pick a $1$ in line $i$, and the only ones are those corresponding to $x_i$ and $\neg x_i$, meaning you have to pick one of the two. You cannot pick both, because you are allowed only $m$ columns in total, so it is just enough to choose a valuation. If you choose both, there will be a $j$ such that neither $x_j$ nor $\neg x_j$ is in your subset.  
> **username_3**: What about: $x_1 \land \neg x_1 \land (x_2 \lor x_3)$? $m = 3$ but one can pick columns $x_1, \neg x_1, x_2$ and make the formula satisfiable. But perhaps I didn't understand well your reduction.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: @dkuper: ok, I understood it.  

---

