Reduction: Vertex Cover to Binary Integer Program (Decision Problem)
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.