# 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  
Although the index size of Algorithm 2 is small, the cost of query answering is expensive, especially when both query vertices have a large degree and do not belong to the vertex cover, \(S\). In fact, the probability that both of the two query vertices do not belong to \(S\) is high in practice, which means that the baseline query algorithm, i.e., Algorithm 3, may not be as efficient as expected. Table 1 shows the ratio of the vertex cover size over that of \(V\) and the probability that only one query vertex belongs to \(S\) and that both query vertices do not belong to \(S\), respectively. From Table 1 we know that the vertex cover could be small sometimes, especially when the graph is sparse, which means that the probability that both query vertices do not belong to \(S\) could be large in practice. For example, for the twitter dataset, the ratio of the vertex cover is 2.33% to that of \(V\). In this case, the probability that one query vertex does not belong to \(S\) is 4.56%, and the probability that both query vertices do not belong to \(S\) is 95.39%, which means that, in most cases, both query vertices do not belong to \(S\); that is, Case 4 will be processed frequently when calling Algorithm 3 to answer queries. Hence, we need to reduce the cost of Case 4 in Algorithm 3 to improve the overall query performance. Different than the existing approach [14] that chooses partial hop vertices to construct a two-hop distance label, our vertex cover is the smallest vertex set that can be used to construct a two-hop distance label to answer all queries without graph traversal. To reduce the cost of Case 4, we propose degree-constraint heuristics to guide the construction of the two-hop distance label. The basic idea is that we do not enlarge the vertex cover but construct a two-hop distance label for more vertices of \(V\setminus S\) when their out- or in-degree is greater than a given threshold, \(d\). In this way, for a given kHRQ, \(u\stackrel{{\gamma k}}{{\rightarrow}}v\), even if both of the two query vertices do not belong to \(S\), we can still directly answer it by calling function query (\(u,\ v,\ k\)) once if \(|out_{G}(u)|>d\ \wedge\ |in_{G}(v)|>d\). For the worst case, where \(|out_{G}(u)|\leq d\ \wedge\ |in_{G}(v)|\leq d\), i.e., Case 4, function query (\(u,\ v,\ k\)) will be called at most \(d^{2}\) times to obtain the result of the query, where \(d^{2}\ll d_{max}^{in}d_{max}^{out}\). **The Algorithm:** Algorithm 4 shows how to construct the degree-constraint two-hop distance label. Compared with Algorithm 2, which generates a two-hop distance label for the vertices of \(S\), Algorithm 4 additionally generates a two-hop distance label for vertices with an out- or in-degree greater than the given threshold, \(d\), even if they do not belong to \(S\), as indicated by lines 4 and 17. Specifically, when performing \(BFS\) from \(u\), we add \([u,\ l_{v}]\) to the in-label \(L_{in}(v)\) of each visited vertex, \(v\), if \(|in_{G}(v)|\ \text{$d$}\) (lines 4 and 14). Similarly, when performing reverse \(BFS\) from \(u\), we add \([u,\ l_{v}]\) to the out-label \(L_{out}(v)\) of each visited vertex, \(v\), if \(|out_{G}(v)|\ \text{$d$}\) (lines 17 and 27). For example, when \(d=1\), Algorithm 4 generates \begin{table}
\begin{tabular}{c c c c} \hline
**Dataset** & 1S1/1V1 (\%) & **Either One (\%)** & **Neither (\%)** \\ \hline Human & 0.97 & 1.92 & 98.07 \\ WikiTalk & 0.72 & 1.43 & 98.56 \\ Twitter & 2.33 & 4.56 & 95.39 \\ Web-uk & 8.48 & 15.53 & 83.75 \\ BerkStan & 41.36 & 48.51 & 34.38 \\ EX6 & 91.14 & 16.15 & 0.79 \\
3 dtube & 95.77 & 8.10 & 0.18 \\ Bio & 95.44 & 8.71 & 0.21 \\ \hline \end{tabular}
\end{table} 
Table 1: The ratio of vertex cover size, \(|S|\), over the number of vertices in the given graph, \(G=(V,E)\) (column 2), and the probability that one or both query vertices do not belong to \(S\) with the assumption that a query is generated by randomly sampling vertex pairs (columns 3–4). the the-hop distance label as shown in Figure 2d.