Proof. Split into three types of vertices: high: \(\deg v > H\) medium: \(\deg v \in [L, H]\), low: \(\deg v < L\).

Case 1: the shortest \(u,v\) path contains a high degree vertex. We capture an approx for these guys as follows: Sample \(100 n/H \log n\) vertices, call the sample \(S_1\). WHP \(S_1\) contains a neighbor of every high degree vertex. BFS out of all the vertices in \(S_1\) to compute \(d(h, v)\) for each \(h\in S_1, v\in V\). Then itterate over \(u,v\in V^2, h\in S_1\) and set \[d(u,v)\le \min_{h\in S_1} d(u,h) + d(h,v).\] This gives a \(+2\) approx for Case 1 pairs.

Case 2: the shortest \(u,v\) path contains a medium degree vertex. Sample \(100n/L \log n\) vertices. Call this \(S_2\). Do a BFS out of each vertex in \(S_2\), this costs \(nH \cdot n/L\). Now we can’t just do what we did in Case 1: it’d be too slow.

Instead, we create a new graph which should hopefully have max-degree \(L\) but not throw away the info we just got from \(S_2\).

First, delete all edges between vertices in \(S_2\) and between all vertices of middle degree. I.e., we only keep edges with one endpoint being a low degree vertex and edges that have one endpoint in \(S_2\) and one endpoint out of \(S_2\). The number of edges in the resulting graph is at most \(nL + nH/L\).

Now, itterate over each vertex \(u\in V\): we will run a fancy SSSP from \(u\). First, we take the above graph and we add edges from \(u\) to each vertex \(x\in S_{2}\) of length \(d(x, u)\) (when I say edge of length \(\ell\) I really mean a path of lenght \(\ell\) because we are doing unweighted APSP). Then BFS out of \(u\). The cost of this BFS is the number of edges in the graph which is \(nL + nH/L\).

We claim that this BFS gives a 2-approx to the shortest paths out of \(u\) (except for the \(v\) for which \((u,v)\) was already handled in case 1).

To see this, first note that all \((u,v)\) paths consisting solely of low degree vertices survive in the modified graph.

Next, observe that if the shortest \((u,v)\) is a path of case 2, i.e., has a medium degree vertex on it, then taking the shortcut from \(u\) to the final medium degree vertex on this shortest \(u,v\) path and then following low degree edges gets us to \(v\). Hence we can also find this sort of path.

Run time over all is

\[ n^{3}/H + n^2H/L + n^2L \le O(n^{7/3}) \] by setting \(H=n^{2/3},L= n^{1/3}\).