3
$\begingroup$

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:

  1. We can convert any decision problem to an optimization problem in polynomial time.
  2. 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)
  3. 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}

$\endgroup$
  • $\begingroup$ I think the comments have gotten a bit astray from helping the poster with their question. Comments are not for extended discussion; this conversation has been moved to chat. Let's take any other tangential discussion to that chatroom. Thanks! $\endgroup$ – D.W. Jan 4 '17 at 22:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I can see that this is a polynomial reduction. But is it a "legal" to add the integer L to the Binary Program? The "official" definition does not contain such a restriction. $\endgroup$ – james.wang Jan 3 '17 at 22:30
  • $\begingroup$ In order to make it a decision problem, I think, we have to add a lower bound (in this case $L$) for the objective function of the binary program (in a case of minimization problem). $\endgroup$ – drzbir Jan 3 '17 at 22:32
  • 1
    $\begingroup$ Integer Programming is an optimization programming – minimize some linear objective function – and the corresponding decision version asks whether the minimum of the objective function is at most something. This answer uses the special case in which the objective function is the sum of the variables. $\endgroup$ – Yuval Filmus Jan 4 '17 at 5:10
  • $\begingroup$ @YuvalFilmus I am pretty sure that adding the constraint to the definition of Binary Integer Programming is not a valid option. BUT we can easily extend A by a row of -1 and add -k at the end of b. The last row then makes sure we don't use too many vertices. $\endgroup$ – james.wang Jan 4 '17 at 17:15
  • $\begingroup$ @james.wang You probably need to state "the" definition of the decision version of binary programming. $\endgroup$ – drzbir Jan 4 '17 at 23:10

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.