How do we construct reductions for NP-Completeness

Question

I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the independent set problem is NP-complete.

In this case, do we start with an instance of the vertex cover problem and show how we can transform this instance into an instance of the independent set problem? Or, do we start with an instance of the independent set problem and transform it into an instance of the vertex cover problem?

I understand the relationship between vertex cover and independent set, however, I am confused on the direction of reduction.

Answer 1

You reduce Independent set to Vertex cover. You want to say that the vertex cover is atleast as hard as Independent set. One could way to remember is you are using a subroutine for vertex cover to solve Independent set. Since Independent set is Np-C you know you know the subroutine you used can't be polynomial. If you do the other way around using a subroutine of Independent set to solve Vertex cover. This does not say anything, as there might be a better way to solve vertex cover and does not show anything.

Answer 2

You need two steps to show that a problem $T$ is NP-complete.

Step 1. Show that $T$ is at least as hard as an NP-complete problem
In other words, show that $T$ is NP-hard. To do this, you choose your favorite NP-complete problem $Q$, and then show that for every instance of $Q$, you can model an instance of $T$ that corresponds to $Q$. Thus, an algorithm which can solve $Q$ in polynomial time can also solve $T$ in polynomial time.

Step 2. Show that a given solution to $T$ can be verified in polynomial time
This is a crucial step if you want to show NP-completeness. For any feasible solution of $T$, you should provide an algorithm that checks whether the solution is true in polynomial time.

Answer 3

To prove a problem B is NP-complete given that problem A is NP-complete (A = independent set, B = vertex cover, in your case), you start with an instance of problem A and transform it into an instance of problem B.

This reduction from A to B implies that (every instance of) problem A can be reformulated as (an instance of) problem B. In other words, problem A is a special case of Problem B, and so Problem B is at least as hard as (or more general than) problem A. If problem A cannot be solved in polynomial time, then problem B also cannot be solved in polynomial time. If B is in NP and if problem A is NP-complete, then so is problem B.