2
$\begingroup$

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?

enter image description here

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Pareod Jan 25 at 15:03
  • $\begingroup$ 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$. $\endgroup$ – Apass.Jack Jan 25 at 18:48
  • $\begingroup$ Thanks, I was not sure why this is not explicitly stated. Apparently it is common knowledge from Linear Programming. $\endgroup$ – Pareod Jan 27 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.