1
$\begingroup$

There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is it true for any problem on graph which has such a greedy algorithm.

$\endgroup$
2
  • $\begingroup$ I don't understand your question. What do you mean by "problem has a greedy algorithm"? I suspect that, if you define what you mean, then the answer to your question is trivial "yes", simply by definition. $\endgroup$ – user114966 Mar 21 at 2:35
  • $\begingroup$ I think you get the right meaning of the question. I just want to get the logic behind the "yes". $\endgroup$ – Subhankar Ghosal Mar 21 at 6:54
1
$\begingroup$

Yes, for every simple graph problem I can think of it's pretty simple to come up with some greedy strategy that gives the optimum if you order your vertices correctly.

Take for example Independent Set. The simplest strategy imaginable for finding an independent set is to fix some ordering $(v_1,\ldots,v_n)$ on the vertices of your graph $G$, putting vertex $v_i$ into your independent set $I$ if it has no neighbors among the vertices that have been put into $I$ so far. This always leads to a maximal independent set, and it's easy to see that every maximal independent set (including those of maximum size) can be generated this way, by just taking an ordering where evey vertex in the set comes before every vertex not in the set.

This strategy also works for other vertex subset problems like Feedback Vertex Set or Dominating Set. Unfortunately, it is pretty uninteresting and unlikely to give much insight into these problems. It's potentially more interesting when such strategies can be devised for more complex problems like Treewidth.

$\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.