6
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I should have been more clearer possibly, but by complement I mean this: Given a decision problem X, its complement X Complement is the collection of all instances s such that s is not in X $\endgroup$ – Teodorico Levoff Mar 28 '15 at 18:27
  • $\begingroup$ @TeodoricoLevoff I have added a short proof that they are not complements. $\endgroup$ – Pål GD Mar 28 '15 at 23:39
-2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You may want to rephrase your sentence. NP-complete is a subset of NP-hard. So it doesn't make sense to say they are np-hard as opposed to np-complete like you did. $\endgroup$ – user643011 May 26 at 17:08

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.