> When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to your problem in quadratic time, your problem has a lower bound of linear time. Howev

> When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to your problem in quadratic time, your problem has a lower bound of linear time. However, when you speed up the reduction to linear time, your lower bound is quadratic time! I think it seems funny because we often intuit that “lower is better” but when it comes to lower bounds higher is better (in the sense of tighter).