Relationship between Independent Set and Vertex Cover

Problem Detail: 

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?

Asked By : Teodorico Levoff

Answered By : Pål GD

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40808