# Reduction from SUBSET-SUM to 0-1-INT-PROG

The 0-1-INT-PROG problem is given an integer $$m \times n$$ matrix $$A$$ and an integer $$m$$-vector $$b$$, is there an integer $$n$$-vector $$x$$ with $$A \cdot x \leq b$$.

I am trying to prove that 0-1-INT-PROG is NP-Hard by reducing SUBSET-SUM to it.

My attempt:

Given an instance of SUBSET-SUM $$<\{a_1, a_2, \cdots, a_n\}, k>$$ we construct an instance of 0-1-INT-PROG $$<[a_1, a_2, \cdots, a_n], [k]>$$.

Claim: $$<\{a_1, a_2, \cdots, a_n\}, k> \in$$ SUBSET_SUM if and only if $$<[a_1, a_2, \cdots, a_n], [k]> \in$$ 0-1-INT-PROG.

proof of forward direction. When there exists a subset $$S' \subseteq S$$ whose sum is $$k$$, for each $$a_i \in S'$$, let $$x_i = 1$$. If $$x_i \not \in S'$$, then $$x_i = 0$$. Then $$x$$ is an $$n$$-vector which achieves $$[a_1, a_2, \cdots, a_n] \cdot x = k$$. So $$<[a_1, a_2, \cdots, a_n], [k]> \in$$ 0-1-INT-PROG.

Question:

When I have tried to prove the other direction I run into a problem. Namely, just because there exists an $$x$$ vector with $$[a_1, a_2, \cdots, a_n] \cdot x \leq k$$, does not imply that there exists a subset $$S' \subseteq S$$ whose sum is $$k$$, because of the less than or equals to.

So how can I approach the backwards direction?

## 1 Answer

Let $$\langle S, k \rangle$$ be an instance of subset sum, where $$S=\{a_1, a_2, \dots, a_n\}$$. Construct an $$0$$-$$1$$-integer program with $$n$$ binary variables $$x_1, \dots, x_n$$ and the following constraints:

\begin{align} a_1x_1+a_2 x_2+ \dots+a_n x_n &\le k \\ -a_1x_1-a_2 x_2 - \dots-a_n x_n &\le -k \end{align}

Or, in matrix form: $$A = \begin{bmatrix} a_1 & a_2 & \dots & a_n \\ -a_1 & -a_2 & \dots & -a_n \end{bmatrix}$$ and $$b=\begin{bmatrix} k \\ -k\end{bmatrix}$$.

If you have a solution $$S' \subseteq S$$ to the subset sum instance, then you can pick $$x$$ as the characteristic vector of $$S'$$ to satisfy the constraints (as you correctly point out in your question). I.e., set $$x_i = 1$$ if and only if $$a_i \in S'$$ so that $$Ax = \begin{bmatrix} k \\ -k\end{bmatrix} = b$$.

On the other hand, if $$Ax \le b$$ then the first constraint is $$a_1 + a_2 + \dots + a_n \le k$$ and second constraint implies $$a_1 + a_2 + \dots + a_n \ge k$$. Then, we necessarily have $$a_1 + a_2 + \dots + a_n = k$$, showing that $$S' = \{ a_i \mid x_i = 1\}$$ is a solution to the subset sum instance.

• So we add a constraint to satisfy the backward direction. I like it, thank you. – Tom Finet Apr 27 at 18:10