I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is mentioned that in expectation, one could solve graph coloring in polynomial time for average cases and only in worst case it is intractable. Does it mean it is easy to attain the minimum bound for coloring in almost all the graphs in polynomial time? How does it work for other problems like dominating set? If number of vertices are n and max degree is \Delta, is it possible to get a solution of size n/(\Delta+1)?
Add a comment
|