There exists a very close and well-known relation between a vertex cover and an independent set in a graph $G(V,E)$ ([1]): if $S$ is an independent set of $G$, then the set $V$ \ $S$ is a vertex cover of $G$. The same complementarity relation holds obviously for a maximum independent set $S$ and the set $C = V$ \ $S$ that is a minimum vertex cover of $G$.

MY question is: Both max independent set (MIS) and min vertex cover (MVC) are NP-hard and they have complementarity relation. Why MIS cannot be approximated to a constant factor in polynomial time (unless P = NP) [2], while MVC is approximable within approximation ratio 2?

Thank you!


[1]C. Berge. Graphs and hypergraphs. North Holland, Amsterdam, 1973. [2]https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Approximation_algorithms

  • $\begingroup$ You might start by consulting the definition, and trying to write down a proposed approximation algorithm for MIS and then try to prove that it has an approximation ratio of 2. Actually work through the math and do the proof and I suspect you'll see what happens. If not, I suggest you edit the question to show your attempt. $\endgroup$ – D.W. Feb 8 '17 at 4:23
  • $\begingroup$ Has been asked and answered before on this site (or perhaps on cstheory.se). $\endgroup$ – Yuval Filmus Feb 8 '17 at 7:03
  • $\begingroup$ Short answer: the reduction doesn't preserve approximation. The longer answer includes the parameters of the NP-hardness reduction for MIS – when you complement the graph, you see that it doesn't give any $(1+\epsilon)$-hardness result for VC. $\endgroup$ – Yuval Filmus Feb 8 '17 at 7:07
  • $\begingroup$ Thanks, DW and Yuval. I will read more about approximation preserving reductions. Thanks again for point me to the right direction. $\endgroup$ – Pepper M Feb 8 '17 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.