0
$\begingroup$

Following what is stated in the question Why is greedy algorithm not finding maximum independent set of a graph?, I have the following question:

Even enumerating and testing all possible choices of the greedy algorithm (namely, when there are two possible choices, test both) and verifying which returns the highest value, can it return an approximate result? (ignoring the computational cost)

$\endgroup$
1
  • 1
    $\begingroup$ Possible candidate for migration to Computer Science? $\endgroup$ Nov 28, 2016 at 9:45

1 Answer 1

1
$\begingroup$

Take the graph in the answer you linked to, and add another vertex G that has an edge to every other vertex except C. Now C has the unique fewest number of neighbours, so it will necessarily be chosen first; then you can choose at most one of A, E, F or the new vertex G since each of these 4 vertices is linked to each of the others by an edge, so the algorithm forces you to produce an independent set of size 2 (either {C, A}, {C, E}, {C, F} or {C, G}). But the same size-3 independent sets as before still exist (e.g. {B, D, F}).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.