# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### recover Phase  
The second phase of Algorithm queue-2 hc, named recover, takes place after Algorithm clean is concluded and considers sets \(\mathtt{OUT}\) and \(\mathtt{IN}\) with the aim of restoring the (possibly broken) cover property for the new graph \(G^{\prime}\). The procedure, shown in Algorithm 4, takes as input also \(G^{\prime}\) and the labeling returned by Algorithm clean, say \(L^{\prime}\), and works by resuming a series of forward and backward shortest-path visits, each considering as root one of the vertices in sets \(\mathtt{OUT}\) and \(\mathtt{IN}\) (i.e., vertices of forward and backward cover graphs), in the order imposed by the vertex ordering. Please note that in the remainder of the paper, given a vertex \(h\in V\), we denote by \(\mathtt{IDX}(h)\) the index of \(h\) in said ordering. Each visit, rooted at some vertex \(h\in\mathtt{OUT}\), has the purpose of checking whether the cover property is satisfied for pairs \(h,v\) for any other \(v\in\mathtt{IN}\) and, in case it is not, to restore it. This is done by visiting only the vertices and the arcs of the forward and backward cover graphs, as discussed in the following. The above is possible thanks to the following property on the labeling, holding after the execution of Algorithm clean. **Property 4**: _Let \(F^{L}_{G}(x,y)\) and \(B^{L}_{G}(x,y)\) the forward and backward cover graphs, respectively. Let \(L^{\prime}\) be the labeling returned by Algorithm 3 when applied to \(G\), to its \(2\)-hop-cover labeling \(L\), as a consequence of a decremental update on arc \((x,y)\in A\). Then, for any pair \(u,v\in V\) such that \(u\
ot\in F^{L}_{G}(x,y)\) or \(v\
ot\in B^{L}_{G}(x,y)\), we have that labeling \(L^{\prime}\) covers pair \(u,v\) also for \(G^{\prime}\), that is \(Q(u,v,L^{\prime})=d_{G^{\prime}}(u,v)\)._  
**Proof. ** By contradiction assume for a pair \(u,v\in V\) such that \(u\
ot\in F^{L}_{G}(x,y)\) (while \(v\) can be of any kind) we have that labeling \(L^{\prime}\) does not cover the pair for \(G^{\prime}\), i.e., \(Q(u,v,L^{\prime})\
eq d_{G^{\prime}}(u,v)\) (the case when \(u\) can be of any kind while \(v\
ot\in B^{L}_{G}(x,y)\) is symmetric). Notice that by Lemma 2 we know that entries in \(L^{\prime}\) are all correct for \(G^{\prime}\). Now, only three cases can occur: (i) \(v\in F^{L}_{G}(x,y)\); (ii) \(v\in B^{L}_{G}(x,y)\); (iii) \(v\
ot\in F^{L}_{G}(x,y)\) and \(v\
ot\in B^{L}_{G}(x,y)\). Notice in fact that by the definition of cover graphs, we cannot have that \(v\in F^{L}_{G}(x,y)\) and \(v\in B^{L}_{G}(x,y)\). **Case (i). ** Both \(u\) and \(v\) are in \(F^{L}_{G}(x,y)\) hence we know that the shortest path in \(G\) between \(u\) and \(v\) does not contain \((x,y)\). Furthermore, it is straightforward to see that the shortest path from \(u\) to \(v\) is made of only vertices in \(F^{L}_{G}(x,y)\) (by contradiction, otherwise \(u\) cannot be in \(F^{L}_{G}(x,y)\)). Hence the hub, say \(h\) covering the pair must be in \(F^{L}_{G}(x,y)\) as well. Therefore \(h\) is not in \(H_{b}(x,y)\) thus it cannot be removed from \(L_{out}(u)\) by Algorithm 5. Moreover, \(L_{in}(v)\) is not changed by Algorithm 5. Hence, we reach the contradiction of \(Q(u,v,L)=Q(u,v,L^{\prime})=d_{G}(u,v)=d_{G^{\prime}}(u,v)\). **Case (ii). ** We know the shortest path from \(x\) to \(v\) in \(G\) included arc \((x,y)\). We can distinguish two sub-cases: either the hub \(h\) covering pair \(u,v\) in \(G\) belongs to such path or not. In the former case, we have that \(h\in H_{f}(x,y)\) and hence also the shortest path from \(u\) to \(h\) in \(G\) must include \((x,y)\). This implies that \(u\in F^{L}_{G}(x,y)\) since there must exist two pairs \((h^{\prime},\delta_{uh^{\prime}})\in L^{\prime}_{out}(u)\) and \((h^{\prime},\delta_{h^{\prime}y})\in L^{\prime}_{in}(y)\) such that \(\delta_{uh^{\prime}}+\delta_{h^{\prime}y}=d_{G}(u,y)\) and \(d_{G}(u,y)=d_{G}(u,x)+w(x,y)\) (that is there must exist an \(h^{\prime}\) that is a hub vertex for pair \(u,y\)) which is a contradiction.