CODEWITHSUNDEEP
graph-theorygreedynp
NITHIN SABU
NITHIN SABU

Reputation: 5

Example where the greedy approach fails for minimum vertex cover problem

A greedy algorithm to find a vertex cover for a given graph would be to greedily select the vertex with the maximum degree and add it to the vertex cover set. Remove the node and all its edges from the graph and keep on repeating the same until there are no edges left.

I understand this is not optimal and the problem is NP hard but can't get the intuition why this is not. Nor could I think of any examples.

I've considered some examples, but it turns out the greedy approach always works. I want an example where this doesn't work and the intuition behind it. Thanks.

Upvotes: 0

Views: 518

Answers (1)

Epsilon delta _
Epsilon delta _

Reputation: 1

Consider a tree , starting with the root node of degree 100, with all the children of the root node being of degree 3 (and that's the tree). The greedy algorithms picks the root + it's children , whereas only the children of the root node is also a vertex cover.

Upvotes: 0

Related Questions