Converting a greedy algorithm to a dynamic programming algorithm

Question

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.

Answer 1

The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to comment on this area, you might find the answer you are looking for among which.

The first one, which is not an answer, but an important notice, is that even though you suggested a (dynamic programming) solution of independent sets, this dynamic program has to consider all partitions of the vertices to find an optimal set. There is probably no dynamic programming solution to this problem that runs in polynomial time, since this will mean that P=NP due to the fact that the maximum independent set problem is NP-complete. However, even though we expect the running time to be exponential, you can solve the problem using only polynomial memory using for example the inclusion exclusion principle (refer to Parameterized algorithms book by Cygan et. al.).

Now back to your question, dynamic programming is usually used to solve generalized versions of greedy problems. For example maximum independent set, maximum matching and minimum dominating set can be found in linear time on trees using greedy algorithms. Greedy algorithms fail however, if the tree is weighted and we are looking for the structure optimizing the total weight. However, these problems can easily be solved in a bottom up dynamic programming manner in linear time, where the dynamic programming states are the subtrees of the given tree.

The third and probably the more interesting part, many problems (even some NP-hard ones) in general graphs admit a dynamic programming solution on the tree decomposition of the given graph. The optimal solutions still have exponential dependence on the tree width. However, they have only polynomial/linear dependence on the size of the input. Usually these problems admit greedy/dynamic programming algorithms on trees, since these algorithms use the fact that a tree decomposition decomposes the graph into small separators, which is trivial in trees. (Again refer to Parameterized Algorithms book by Cygan et. al.)