I think the Goal Bounding Gate optimisation he talks about could help with both: it's still O(N²), but if N is limited to those gateway nodes that would cut down on costs tremendously. But that all depends on whether it's cheap to find those gateway nodes automatically.
