# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 3 A Vertex-Cover-Based Approach
### Index Construction
#### 3.2.3 The Degree-Constraint-Based Two-Hop Label
Compared with the baseline two-hop distance label shown in Figure 2c with respect to Algorithm 2, a new out-label, \(L_{out}(f)\), is only constructed for vertex \(f\). However, in this case, the benefit is obvious; we can guarantee that, for any query, function query \((u,\ v,\ k)\) is called only once. ```
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\vee|in_{G}(v)|\ )\ d)
5\(l_{v}\leftarrow\) the distance from u to v calculated through \(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\vee|out_{G}(v)|\ )\ d)
18\(l_{v}\leftarrow\) the distance from \(u\) to 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\ \mathrm{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 4** genVCIndex\({}^{+}\ (G=(V,E),d)\)  
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, for Algorithm 4, the time complexity is \(O(|S|(|V|+|E|)L)\). Additionally, the size of the distance label is \(O(|S|\ L)\), where \(S=S\cup S_{1}\cup S_{2}\subseteq V\); \(S_{1}\) is a set of vertices where each vertex has an out-degree \(>d\), and \(S_{2}\) is another set of vertices where each vertex has an in-degree \(>d\). As \(|\ S|\leq|S|\leq|V|\), the degree-constraint two-hop distance label achieves higher efficiency with a larger index size than that of Algorithm 2. **Queries Answering:** Based on the two-hop distance label constructed with Algorithm 4, we answer queries using Algorithm 5. Compared with the baseline algorithm, i.e., Algorithm 3, Algorithm 5 also answers a query in four cases with Equation (4). The difference lies in that, in each case, we not only check whether \(u\) or \(v\) belongs to \(S\), but we also check whether the number of out-neighbors (in-neighbors) of \(u(v)\) is greater than the predefined threshold, \(d\) (lines 1 and 2). In this way, we enlarge the probability that the given query is answered with the first three cases, which, in turn, reduces the probability of Case 4. It is worth noting that, when \(d=1\), we can answer any query by calling function query \((u,\ v,\ k)\) once, which is as efficient as generating a two-hop distance label for all the vertices but has smaller index size. When \(d>1\), to answer the given query, \(u\stackrel{{\mathcal{T}}}{{\rightarrow}}v\), Algorithm 5 will call function query \((u,\ v,\ k)\) once for Case 1, at most \(d\) times for Case 2 and Case 3, and at most \(d^{2}\) times for Case 4. Since the probability of Case 4 in Algorithm 5 is small compared with that in Algorithm 3, the query performance can be improved as shown by our experimental results. Example 4 continues Example 3, where query \(g\overset{\ref{thm:22}}{\rightarrow}f\), and corresponds to Case 2, but here it corresponds to Case 1 due to \(d=1\). Query \(a\overset{\ref{thm:22}}{\rightarrow}f\) corresponds to Case 4 in Example 3, but here it corresponds to Case 3. Additionally, as \(d=1\), any case of Algorithm 5 will call function query \((u,\ v,\ k)\) only once for any query. Therefore, compared with Algorithm 3, the calling times of function query \((u,\ v,\ k)\) can be reduced with Algorithm 5.