I'm not entirely sure I see the value of this. Note that it doesn't tell us much about the state of the world, but rather more about the historical order in which these problems were inducted into the NP-completeness club. And by the time enough data points have been added to the picture to cover a meaningful fraction of the NP-complete problems that have been studied, will it even be possible to make sense of the humongous graph?
There are meaningful distinctions within NP-complete problems, such as whether they are easy to approximate. Perhaps if the graph incorporated that information, I can see this going somewhere..
It is incredibly useful for us kids just now learning about algorithms and trying to see if the problem described in the text book is reducible to a known NPC problem.
There are meaningful distinctions within NP-complete problems, such as whether they are easy to approximate. Perhaps if the graph incorporated that information, I can see this going somewhere..