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} &amp; a_{1,2} &amp; \dots &amp; a_{1,n} \\
     a_{2,1} &amp; a_{2,2} &amp; \dots &amp; a_{2,n} \\
     \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
     a_{r,1} &amp; a_{r,2} &amp; \dots &amp; a_{r,n} \\
     -1 &amp; -1 &amp; \dots &amp; -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}
    &amp; \text{minimize}
    &amp; &amp; \sum_{v \in V} x_v\\
    &amp; \text{subject to}
    &amp; &amp; x_u+x_v\geq 1 \text{ for all } \{u,v\} \in E\\
    &amp; &amp; &amp; 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.