$SET-COVER\leq_pIP$

Question

Let:

$IP=\left \{ \left \langle A,b \right \rangle \right \}:$ $A$ is a $m\times l$ matrix over the integers, $b$ is a vector of $m$ integers and there exists a vector $x$ of $l$ integers s.t $Ax\geq b$.

Note that $Ax$ and $b$ are both m-dimensional vectors.

When writing $Ax\geq b$ the meaning is the inequality holds in each coordinate.

$SET-COVER=\left \{ \left \langle U,S_1,\ldots,S_m,k \right \rangle \right \}:$ $U$ is a set of integers, $S_1,\ldots,S_m\subseteq U$ and there exists a subset $A\subseteq \left \{ 1,\ldots,m \right \}$ s.t $\left | A \right |=k \; \wedge \; \bigcup_{i\in A}S_i=U$.

The question asked to show $SET-COVER\leq_pIP$

I'm stuck mainly on the part of $x$ in $IP$ - all my attempts converged to failure because I was able to increase $x$ as much as I wanted in order to get $Ax\geq b$.

Answer 1

Given $(U, S_1, …, S_m, k)$ an input of Set-Cover, with $U = \{1, …, n\}$, consider an $n\times m$ matrix with $0$-$1$ coefficients, such that $A_{ij}$ represents $i\in S_j$.

Consider $b$ an $n$-vector with only $1$'s.

Can you see the link between the two problems?

Note that this is not the complete solution, since you have to modify those matrices to add a condition on $k$.

First, you want coefficients of $x$ to be either $0$'s or $1$'s. That means that for all $i$, $x_i \geqslant 0$ and $-x_i\geqslant -1$.

You just need to add $2m$ lines in the matrix $A$, each containing either $1$ or $-1$ at the right position, and $2m$ lines to the vector $b$, with either $0$ or $1$.

For the condition that the subset of $[\![1,m]\!]$ must be of size $\leqslant k$, that means that $\sum x_i\leqslant k$.

How to do it? Add a line of $-1$ in the matrix $A$, and a line $-k$ in the matrix $b$. Indeed, $\sum\limits_{i=1}^m(-1)\times x_i \geqslant -k\Leftrightarrow \sum\limits_{i=1}^mx_i \leqslant k$.