Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover.
Does this imply that the complement of the independent set problem is the vertex cover problem?
Well, strictly speaking it's not the complement; co-VC is co-NP-complete whereas Independent Set is NP-complete. If they were the same, we would know that co-NP was equal to NP, which we do not, and indeed most people believe they are not.
But an easy way of seeing that they are not the same if to consider $(K_4, 2)$, the complete graph on four vertices) which is neither a yes-instance of Vertex Cover nor of Independent Set. Similarly, the instance $(K_2,1)$ is a yes-instance for both.
However, they are related in the following way. A set of vertices $C \subseteq V(G)$ of a graph $G$ is a vertex cover if and only if $V(G) \setminus C$ is an independent set. This is easy to see; for every endpoint of an edge, at least one vertex must be in $C$ for $C$ to be a vertex cover, hence not both endpoints of an edge are in $V(G) \setminus C$, so $V(G) \setminus C$ is an independent set. This holds both directions.
So $(G,k)$ is a yes instance for Vertex Cover (a minimization problem) if and only if $(G,n-k)$ is a yes instance for Independent Set (a maximization problem).
You may check out this link:
http://www.hananayad.com/teaching/syde423/IndependentSet.pdf
According to this one, both are equally hard (NP-complete), however, optimization version of each problem is NP-hard.
