2
$\begingroup$

The minimal vertex cover problem has a 2-approximation algorithm.

We can reduce the maximal independent set problem to the minimal vertex cover problem as shown here.

Does this mean that I can use the $2$-approximation for minimal vertex cover to get a $1/2$-approximation for maximal independent set?

My approach:

// is this a 1/2-approximation algorithm?
approxAlgForMaxIS(Graph G) {
    minVC = computeMinVC(G);
    maxIS = G.V - minVC;   // remove all vertices in the minVC from G
    return maxIS
}
$\endgroup$
  • $\begingroup$ The way to tell whether this works is to try to prove it works! It sounds like you have an algorithm in mind. Now try to prove that it is a 1/2-approximation. Are you able to prove it? What efforts have you made? What progress have you made so far and where specifically did you get stuck? $\endgroup$ – D.W. Sep 16 '17 at 14:06
  • $\begingroup$ Asked a few times before... $\endgroup$ – Yuval Filmus Sep 16 '17 at 14:27
  • $\begingroup$ @YuvalFilmus could you please point me to one of those questions? $\endgroup$ – Anna Vopureta Sep 16 '17 at 14:34
  • $\begingroup$ Some of them appear in the "related" pane. All of them would mention "vertex cover", "independent set", and "approximation". $\endgroup$ – Yuval Filmus Sep 16 '17 at 14:36
3
$\begingroup$

No, unfortunately this doesn't work. Denote by $\newcommand{\VC}{\mathrm{VC}}\VC$ the size of a minimum vertex cover and by $\newcommand{\IS}{\mathrm{IS}}\IS$ the size of a maximum independent set, so that $\VC+\IS=n$. The approximation algorithm for $\VC$ produces a vertex cover $C$ whose size satisfies $|C| \leq 2\VC$. The complement of $C$ is an independent set $I$ whose size satisfies $$ |I| = n-|C| \geq n-2\VC. $$ Unfortunately, $n-2\VC$ can be much smaller than $n-\VC$, and there's no constant lower bound on the ratio $$ \frac{n-2\VC}{n-\VC}. $$

As an example, let's see how the algorithm which picks a maximal matching fares on a graph consisting of a matching on $n$ vertices. The minimum vertex cover has size $n/2$, and so the maximum independent set has size $n/2$. The maximal matching algorithm picks all edges in the graph and then all vertices contained in them – in other words, it picks all vertices. It thus gives a vertex cover of size $n$, which corresponds to an independent set of size 0.

This difference between vertex cover and independent set is reflected in the fact that it is NP-hard to approximate independent set to within $n^{1-\epsilon}$, for any $\epsilon > 0$.

$\endgroup$

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.