Awesome article. My take on this is that 'interesting' graph problems tend to be NP-(.*), or reduce to a handful of well-known standards. Some of these standa

Awesome article. My take on this is that 'interesting' graph problems tend to be NP-(.*), or reduce to a handful of well-known standards. Some of these standards, like breadth-first traversal, work quickly and are therefore standard interview questions. Other standard solutions, like page-rank, are effectively eigenvalue problems which take N^3 time to find the true solution. N^3 is generally too slow for large-scale production systems, though, so we end up introducing some randomness and battering the algorithm into an almost-linear time approximation algorithm that can run on a thousand machines no problem; this is where Pregel comes from. As someone who loves playing with graph algorithms, I would absolutely love to be wrong in this world-view, and learn that mine eyes have been carefully shielded from the beautiful variety of graph problems that aren't in one of these three classes... So I'll make a resolution to try to keep my eyes open for surprises in 2016.