Reduction: Vertex Cover to Binary Integer Program (Decision Problem)

I am stuck with the following task:
Show that the Decision Problem "Vertex Cover" is polynomial-time reducible to the Decision Problem "Binary Integer programming".

I have the feeling that there must be a very easy way.

My approach until now:

• We can convert any decision problem to an optimization problem in polynomial time.

• We can reduce the optimization problem of vertex cover to a linear program in polynomial time. (https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness)

• We can convert any optimization problem to a decision problem in polynomial time.

Is this approach ok? And/Or is there a better/easier way?

kind regards
James

EDIT: I think the following solution should work

Let $a_{i,j}$ be 1 if vertex $j$ is connected with edge $i$ and otherwise 0. Let $r=|E|$ and $n=|V|$.

A=
\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots & a_{1,n} \\
a_{2,1} & a_{2,2} & \dots & a_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{r,1} & a_{r,2} & \dots & a_{r,n} \\
-1 & -1 & \dots & -1 \\
\end{bmatrix}

Let $b_i = 1$ $\forall i \in 1..r$

b=
\begin{bmatrix}
b_1 \\
b_2 \\
\vdots \\
b_r \\
-k \\
\end{bmatrix}

Vertex Cover (Decision Version):

• Given a graph $G=(V,E)$ and a positive integer $K$. The decision vertex cover problem asks: Does $G$ contains a vertex cover of size $K$ or less?

Binary Program (Decision Version):

• Given a matrix $\mathbf{A}$ of size $m\times n$, a vector $\mathbf{b}$ of size $m$ and a positive integer $L$. Define the decision version of Binary Program as: Is there a vector $\mathbf{x}\in\{0,1\}^n$ of $L$ nonzeros or less such that $\mathbf{A}\mathbf{x}\geqslant\mathbf{b}.$

You could write the optimization version of vertex cover as a Binary Program as follows: Let $x_v$ be a binary variable that is equal $1$ if vertex $v$ is selected, and, $0$, otherwise.

\begin{align}
& \text{minimize}
& & \sum_{v \in V} x_v\\
& \text{subject to}
& & x_u+x_v\geq 1 \text{ for all } \{u,v\} \in E\\
& & & x_{ v }\in\{0, 1\}, \forall v\in V.
\end{align}

You can easily check that this Binary Program indeed finds a vertex cover of minimum size.

Now, just set $L=K$, $m=|E|$, $n=|V|$, the vector $\mathbf{b}=[1,1,\ldots,1]^\top$ and the matrix $\mathbf{A}=[a_{ev}]_{\forall\,e\in E,v\in V}$ as

$$a_{ev}=\begin{cases}1,\text{ if } v\in e\\0, \text{ otherwise}\end{cases}$$

This is, cearly, a polynomial-reduction from Vertex Cover to Binary Program.

StackExchange Computer Science Q#68232, answer score: 3