# 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
**Queries Answering:** With the two-hop distance label constructed with Algorithm 2, we answer a kHRQ using Algorithm 3. There are four cases that we need to consider as indicated by Equation (3) and Algorithm 3. Case 1: both \(u\) and \(v\) belong to the vertex cover, \(S\) (line 1 of Algorithm 3). In this case, we answer this query directly by comparing the two-hop distance labels of \(u\) and \(v\) to obtain the length of the path from \(u\) to \(v\) as indicated by Equation (1) and function query \((u,\;v,\;k)\) in Algorithm 3. Case 2: \(u\) belongs to \(S\), but \(v\) does not (line 3). In this case, we need to answer for each in-neighbor \(w\) of \(v\) whether \(u\) can reach \(w\) in \(k-1\) steps as indicated by lines 4-9. If there exists an in-neighbor \(w\) such that \(u\stackrel{{\mathcal{R}_{k}\to}}{{\rightarrow}}w\) returns TRUE, then we know \(u\stackrel{{\mathcal{R}_{k}\to}}{{\rightarrow}}v\) returns TRUE in line 6; otherwise, the result is FALSE. Case 3: \(v\) belongs to \(S\), but \(u\) does not (line 10). In this case, we need to answer for each out-neighbor \(w\) of \(u\) whether \(w\) can reach \(v\) in \(k-1\) steps as indicated by lines 11-16. If there exists an out-neighbor \(w\) such that \(w\overset{\mathcal{I}k-1}{\rightarrow}v\) returns TRUE, then we know \(u\overset{\mathcal{I}k}{\rightarrow}v\) returns TRUE in line 13; otherwise, the result is FALSE. ```
1 Case 1:\(u\in S\,\wedge\,v\in S\)
2 return query (\(u,v,k\))
3 Case 2:\(u\in S\,\wedge\,v\
otin S\)
4 foreach\(w\in\mathit{in}_{G}(v)\)do
5 if (query \((u,w,\,k-1)\) = TRUE) then
6 return TRUE
7 endif
8 endfor
9 return FALSE
10 Case 3:\(u\
otin S\,\wedge\,v\in S\)
11 foreach\(w\in\mathit{out}_{G}(u)\)do
12 if (query \((w,\,v,\,k-1)\) = TRUE) then
13 return TRUE
14 endif
15 endfor
16 return FALSE
17 Case 4:\(u\
otin\mathcal{S}\wedge\,v\
otin S\)
18 foreach\(s\in\mathit{out}_{G}(u)\)do
19 foreach\(t\in\mathit{in}_{G}(v)\)do
20 if (query \((s,t,k-2)\) = TRUE) then
21 return TRUE
22 endif
23 endfor
24 endfor
25 return FALSE
26 Function query \((u,v,k)\)
27\(\mathit{C}_{out}\leftarrow\{w|[w,\,d(u,w)]\in\mathit{L}_{out}(u))\}\)
28\(\mathit{C}_{in}\leftarrow\{w|[w,\,d(w,v)]\in\mathit{L}_{in}(v))\}\)
29\(\mathit{C}\leftarrow\mathit{C}_{out}\bigcap\mathit{C}_{in}\)
30 if (\(\mathit{C}\
eq\varnothing\)) then
31\(l\leftarrow(\mathit{min}_{w\in\mathit{C}}(d(u,w)+d(w,\,v)))\)
32 if (\(l\,\leq\,k\))then
33 return TRUE
34 endif
35 endif
36 return FALSE
```  
**Algorithm 3**_VCRea (u,v,k)_  
Case 4: both \(u\) and \(v\) do not belong to \(S\) (line 17). In this case, we need to check for each pair of vertices \(s\) and \(t\), whether \(s\) can reach \(t\) in \(k-2\) steps, where \(s\) is an out-neighbor of \(u\) and where \(t\) is an in-neighbor of \(v\), as indicated by lines 18-25. If there exists a vertex pair such that \(s\overset{\mathcal{I}k-2}{\rightarrow}t\) returns TRUE, then we know \(u\overset{\mathcal{I}k}{\rightarrow}v\) returns TRUE in line 21; otherwise, the result is FALSE. **Example 3:**_Consider the graph in Figure 1. Figure 2c shows its two-hop label. As both \(d\) and \(i\) belong to \(S=\{b,\,d,\,g,\,i\}\), query \(b\overset{\mathcal{I}2}{\rightarrow}i\) corresponds to Case 1, which can be answered by first computing \(d(b,\,i)\) using Formula (1). Since \(d(b,\,i)\) = 4 by Formula (1), we know that the result is FALSE. For another example, as \(h\,\
otin\,S\), query \(g\overset{\mathcal{I}2}{\rightarrow}f\) corresponds to Case 2. Similarly, query \(a\overset{\mathcal{I}2}{\rightarrow}i\) corresponds to Case 3, and query \(a\overset{\mathcal{I}2}{\rightarrow}f\) corresponds to Case 4, which needs to call function query \((u,\,v,\,k)\) twice due to the fact that the out-degree of \(a\) is one and due to fact that the in-degree of \(f\) is two._Let \(L\) be the number of entries in the longest two-hop label; the cost of function query \((u,\ v,\ k)\) is \(O(L)\).