# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 3 A Vertex-Cover-Based Approach
### Index Construction
#### 3.2.2 The Baseline Two-Hop Distance Label  
In this section, we discuss how to build the smallest two-hop distance label based on the vertex cover, \(S\). Specifically, our approach takes the vertices of \(S\) as hop vertices and only generates a two-hop distance label for the vertices in \(S\) as shown by Algorithm 2. In Algorithm 2, we process all the vertices in the vertex cover, \(S\), to generate a two-hop distance label. It first calls Algorithm 1 in line 1 to compute the vertex cover, \(S\). In lines 2-29, it processes all the vertices of \(S\) in the same order as they entered \(S\). For each vertex, \(u\), Algorithm 2 performs _BFS_ in lines 3-15 and reverse _BFS_ in lines 16-28. During the _BFS_ and reverse _BFS_ of \(u\), it only constructs a two-hop distance label for the vertices that belong to \(S\). Specifically, for each vertex, \(v\), being visited when performing _BFS_, we first check whether \(v\) belongs to \(S\) in line 4. If \(v\in S\) (line 4 holds), we first obtain the distance from \(u\) to \(v\) through _BFS_ from the unvisited vertices in line 5. Then, we compute the distance in lines 6-10 using the current distance label as indicated by \(min_{w\in C}(d(u,w)+d(w,\ v))\). If there exists a path with a length greater than the length of a path computed by the current label (line 10 holds), it means that \(v\) is useless when computing the length of the paths from \(u\). Thus, we do not need to process \(v\) anymore and terminate the processing of \(v\) in line 11. Otherwise, we add the distance entry, \([u,\ l_{v}]\), into label \(L_{in}(v)\). After performing _BFS_ in lines 3-15, we perform reverse _BFS_ from \(u\) in lines 16-28. In line 17, we first check whether the currently visited vertex, \(v\), belongs to \(S\). If YES (line 17 holds), we first obtain for the path from \(v\) to \(u\) its length, \(l_{v}\), in line 18. Then, in lines 19-23, we check whether the newly computed path is less than \(l_{v}\). If line 23 holds, it means that \(v\) is useless. Therefore, we terminate the processing of \(v\) in line 24. Otherwise, we need to then add the distance entry, \([u,\;l_{v}]\), into the distance label \(L_{out}(v)\). For example, assume that the vertex processing order is \(d,\;g,\;b,\;i\) and that we have the two-hop distance label shown in Figure 2c. ```
1\(S\leftarrow\) CompVC (\(G=(V,E)\)) /*Algorithm 1*/
2 foreach (vertex \(u\;\in\;S\)) do
3 for each vertex, \(v\), being visited when performing \(BFS\) from \(u\)
4 if\((v\;\in\;S)\)
5\(l_{v}\leftarrow\) the distance from \(u\) to \(v\) by \(BFS\)
6\(C_{out}\leftarrow\{w[|w,\;d(u,w)]\;\in\;L_{out}(u))\}\)
7\(C_{in}\leftarrow\{w[|w,\;d(w,v)]\;\in\;L_{in}(v))\}\)
8\(C\leftarrow\)\(C_{out}\)\(\bigcap\)\(C_{in}\)
9 if\((C\
eq\varnothing)\)then
10 if\((l_{v}>\min_{w\in C}\;(d(u,w)+d(w,v)))\)then
11 terminate the processing of \(v\)
12 endif
13 endif
14 add\([u,\;l_{v}]\) into \(L_{in}(v)\)
15 endif
16 for each vertex, \(v\), being visited when performing reverse \(BFS\) from \(u\)
17 if\((v\;\in\;S)\)
18\(l_{v}\leftarrow\) the distance from \(u\) to \(v\) by reverse \(BFS\)
19\(C_{out}\leftarrow\{w[|w,\;d(v,w)]\;\in\;L_{out}(v))\}\)
20\(C_{in}\leftarrow\{w[|w,\;d(w,u)]\;\in\;L_{in}(u))\}\)
21\(C\leftarrow\)\(C_{out}\)\(\bigcap\)\(C_{in}\)
22 if\((C\
eq\varnothing)\)then
23 if\((l_{v}>\min_{w\in C}\;(d(v,w)+d(w,u)))\)then
24 terminate the processing of \(v\)
25 endif
26 endif
27 add\([u,\;l_{v}]\) into \(L_{out}(v)\)
28 endif
29 endfor
```  
**Algorithm 2** genVCIndex \((G=(V,E))\)  
**Analysis:** Let \(L\) be the number of entries in the longest distance label \((L\;\leq|S|)\). The cost of lines 6-10 is \(O(L)\); thus, the time complexity of Algorithm 2 is \(O(|S|(|V|+|E|)L)\). Additionally, the size of the distance label is \(O(|S|L)\). In practice, \(S\) is usually much smaller than \(V\); thus, it is reasonable that, based on our approach, the index size and index construction time could be reduced, which is verified by our experimental results in Section 4.