Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)
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}).
