2
$\begingroup$

Let's I have to make the following reduction:

$$\text{CLIQUE}\le_p \text{VERTEX-COVER}$$

The technique of building the reduction is -

  1. Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in polynomial time.
  2. Building a new graph, in which I say that if a $\text{VERTEX-COVER}$ exists of size $k$, then in the original graph, a $\text{CLIQUE}$ of size $k$ exists?

I just want to understand the technique of these proofs.

$\endgroup$
0
$\begingroup$
  1. Assume you can find a $vertex-cover$ of size $k$, in polynomial time.

Actually, this step is not correct. When we show that $A \le_p B$, where $A$ and $B$ are languages (also known as decision problems), we do not assume that either $A$ or $B$ can be solved in polynomial time. What we do is "reduce" problem $A$ to problem $B$: that means that we take an instance of problem A, and return an instance of problem $B$. The part that has to be polynomial time is this "reduce" function.

In other words, it's possible that $A$ and $B$ are both really "hard" -- they can't be done in polynomial time, or maybe they aren't even decidable. But what we show is that the reduction is polynomial time.

So what is this "reduction" that we have to show is polynomial time? You mentioned part of it:

  1. Building a new graph, in which I say that if a $vertex-cover$ exists of size $k$, then in the original graph, a $clique$ of size $k$ exists?

That's half. You also have to show that if a vertex-cover doesn't exist of size $k$, then in the original graph, a clique of size $k$ doesn't exist.

To summarize: when doing a reduction from $A$ to $B$ ($A \le_p B$), here are the three things you should show:

  1. If the output of the reduction is in $B$, then the input is in $A$. (For example, if a vertex-cover exists in the output, then in the original graph, a clique exists.)

  2. If the output of the reduction is not in $B$, then the input is not in $A$. (For example, if a vertex-cover does not exist in the output, then in the original graph, a clique does not exist).

  3. The whole reduction -- which takes instances of problem $A$ to instances of problem $B$ -- runs in polynomial time.

$\endgroup$

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.