# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### Profiling of Algorithm bidir-2 hc
_Inductive Step._ We consider the case when \(|Q|=k+1\). Observe that the next extracted vertex \(v\) must be a neighbor of some vertex, say \(v^{\prime}\), processed in one of the previous \(k\) iterations, as otherwise \(v\) would not be in \(Q\). Moreover, \(d_{G}(v,y)=d_{G}(v,v^{\prime})+d_{G}(v^{\prime},x)+w(x,y)\) as \(v\) is the one with minimum priority. Therefore, we have that, if vertex \(v\) is in \(F^{L}_{G}(x,y)\), in line 18, set \(\{h^{\prime}\in V\ :\ h^{\prime}\in L_{out}(v)\wedge h^{\prime}\in L_{in}(y), \delta_{vh^{\prime}}+\delta_{h^{\prime}y}=\delta\}\) must be not empty, with \(\delta=\delta_{vh}+\delta_{hy}\) for some \(h\in\{h^{\prime}\in V\ :\ h^{\prime}\in L_{out}(v)\wedge h^{\prime}\in L_{in}(y), \delta_{vh^{\prime}}+\delta_{h^{\prime}y}=\delta\}\) (since any pair of vertices is covered by some hub \(h\) in \(L\) for \(G\)) and \(d_{G}(v,y)=d_{G}(v,v^{\prime})+d_{G}(v^{\prime},x)+w(x,y)=d_{G}(v,h)+d_{G}(h,y)\). Thus, the claim holds. Then, we prove that all entries left in the labeling by Algorithm clean are correct for \(G^{\prime}\). Lemma 2: _Let \(L\) be a minimal well-ordered \(2\)-hop-cover labeling of a graph \(G\). Let us assume that an arc \((x,y)\) of \(G\) undergoes a decremental update and let \(G^{\prime}\) be the resulting graph. Let \(L^{\prime}\) the labeling returned by Algorithm 3. Then, for any \(v\in V\), all entries \((h,\delta_{vh})\in L^{\prime}_{out}(v)\) are correct for \(G^{\prime}\), that is \(\delta_{vh}=d_{G^{\prime}}(v,h)\). Symmetrically, for any \(v\in V\), all entries \((h,\delta_{vh})\in L^{\prime}_{in}(v)\) are correct for \(G^{\prime}\), that is \(\delta_{hv}=d_{G^{\prime}}(h,v)\)._  
Proof. : By contradiction, assume that there exists some entry \((h,\delta_{vh})\in L_{out}(v)\), for some \(h\in V\), that does not correspond to a shortest path in \(G^{\prime}\) after executing Algorithm 3, i.e., such that \(\delta_{vh}\
eq d_{G^{\prime}}(v,h)\). Since \(\{x,y\}\) undergoes a decremental update, we must have that \(\delta_{vh}<d_{G^{\prime}}(v,h)\), as otherwise a first contradiction would be reached (either a decremental update is not increasing the distance or \(\delta_{vh}=d_{G^{\prime}}(v,h)\)).Moreover, we know \(\delta_{vh}=d_{G}(v,h)\) since \(L\) is a 2-hop-cover labeling therefore \(v\) must be a descendant of \(x\) in a shortest-path arborescence of \(G\) rooted at \(h\), as otherwise \((h,\delta_{vh})\) would not be in \(L_{out}(v)\). Hence, by Lemma 1, vertex \(v\) must be in the forward cover graph \(F^{L}_{G}(x,y)\) and hence is processed by Algorithm 3 in line 19. Thus, two cases can occur: either \(h\in H_{f}(x,y)\) or not. In the former case, the label entry is removed by Algorithm clean, which is again a contradiction. In the latter case, instead, we have that the shortest path from \(x\) to \(h\) in \(G\) did not contain \((x,y)\), hence \(d_{G}(x,h)=d_{G^{\prime}}(x,h)\). Now, on the one hand, if the shortest path from \(v\) to \(h\) in \(G\) included \((x,y)\), we reach a contradiction. In fact, \((h,\delta_{vh})\) is removed, since \(d_{G}(v,h)=d_{G}(v,x)+w(x,y)+d_{G}(y,h)\) and hence \(v\in F^{L}_{G}(x,y)\) and \(h\in H_{f}(x,y)\). On the other hand, if the shortest path from \(v\) to \(h\) in \(G\) did not include \((x,y)\), we obtain the contradiction of \(\delta_{vh}\) being correct, since \((x,y)\) not being on the shortest path from \(v\) to \(h\) implies \(d_{G}(v,h)=d_{G^{\prime}}(v,h)\). A symmetric argument can be used to show that all entries \((h,\delta_{hv})\in L_{in}(v)\) are correct, for any \(h\in V\), by considering the shortest-path arborescence of \(G^{T}\) and set \(H_{b}(x,y)\). Finally, we prove a slightly stronger property, which is the minimality of removals. Specifically, we can prove that no correct label entry is removed by Algorithm 3, i.e., the number of removals is minimal to remove all entries that do not correspond to shortest paths in \(G^{\prime}\).