# What is wrong with this reduction from vertex cover to binary programming?

I am trying to polynomial-time reduce the decision version of vertex cover to the decision version of binary programming. Here are the problem statements.

Vertex Cover Decision Problem

Instance: A graph $$G=(V,E)$$ and an integer $$k$$.

Question: Does $$G$$ have a vertex cover of size at most $$k$$?

Binary Programming Decision Problem

Instance: An integer $$m \times n$$ matrix $$A$$, an integer $$m$$-vector $$b$$, and an integer $$l$$.

Question: Is there a a 0-1 $$n$$-vector $$x$$ with at most $$l$$ 1's such that $$Ax \geq b$$? Here $$||x||_1= \sum_{i=1}^{n}x_i$$.

I found a supposed transformation here that makes $$A$$ an $$|E| \times |V|$$ matrix, where $$a_{e,v}=1$$ if edge $$e$$ is incident on vertex $$v$$ and $$0$$ otherwise. It also sets $$b$$ to an all 1's vector and $$l=k$$.

This transformation works in one direction: if you have a vertex cover you can build $$x$$ by letting $$x_v=1$$ if vertex $$v$$ is included in the vertex cover and $$0$$ otherwise. However, in the other direction I can easily create an example where $$Ax \geq b$$ but the 1's in $$x$$ do not create a vertex cover in the induced graph. Can anyone provide a hint as to how to correct this?

Your example does not hold since the first entry of $$Ax$$, 0 is smaller than 1, the first entry of $$b$$.
$$\begin{array}{c c c} &Ax & &b\\ & \begin{bmatrix}0 \\1 \\2 \\1 \\1\end{bmatrix} & \not\ge\ & \begin{bmatrix}1 \\1 \\1 \\1 \\1 \\\end{bmatrix} \end{array}$$
Please note the condition $$Ax\ge b$$ means every entry in $$Ax$$ is no less than the corresponding entry in $$b$$. In term of the corresponding problem, the vertex cover problem, it means every edge is incident to at least 1 vertex. It is not about the $$L_1$$ norm; otherwise, it should be written as, for example, $$||Ax||_1\ge ||b||_1$$.
Yes, we want to minimize the number of 1's in $$x$$, which is the same as minimizing $$||x||_1$$. However, the condition $$Ax\ge b$$ is a requirement on $$x$$. The requirements on the variable that are usually read as "subject to ..." and the objective function could be seen as irrelevant or independent to each other.
• I assumed that since we want to minimize the number of 1's in $x$, which is essentially minimizing $||x||_1$, that the comparison $Ax \geq b$ is based on the $L_1$ norm as well. Is this not the case? If we apply the $L_1$ norm then $Ax=b=5$. – Pareod Jan 25 at 15:03
• No, the comparison $Ax\ge b$ is not about the $L_1$ norm. It means every entry in $Ax$ is no less than the corresponding entry in $b$. – Apass.Jack Jan 25 at 18:48