# Converting a greedy algorithm to a dynamic programming algorithm

Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:

First, find a maximum indpendent set of vertices in the graph, and give it one color.

Next remove the set of vertices found in the previous case from the graph, and repeat the same process till I reach the empty set.

Now, I agree that it is hard to find the maximum independent set of an arbitrary graph. But, is there a way where this greedy sort of simple algorithm could be converted to a dynamic programming type algorithm? Say, may be we could decompose the graph into two simpler graphs and find maximal independent sets in each of the subgraphs, and then try to club the two individual independent sets to form a larger independent set by checking for adjacency. Is such a kind of 'conversion' from greedy to dynamic programming or vice-versa always possible? Can this change the complexity of the problem radically? Thanks beforehand.

• Why would you want to do this? Perchance you have a particular algorithm in mind? Commented Oct 21, 2019 at 14:40
• @YuvalFilmus actually, my problem in mind is a graph coloring problem for a certain structured graph. I would want to do this as I wish to prove an upper bound on the chromatic number. The greedy approach may not be useful my case, in which case, I thought that subdividing the problem could help Commented Oct 21, 2019 at 15:15
• Perhaps you should ask your actual question as a new question. You might get more helpful answers. Commented Oct 21, 2019 at 15:17