# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 3 A Vertex-Cover-Based Approach
### Overview
Note that, in Equation (3), Equation (2) may need to be called \(|out_{G}(u)|\times|in_{G}(v)|\) times in the worst case to answer the given query \(u\stackrel{{ 2k}}{{\rightarrow}}v\). \[u\stackrel{{ 2k}}{{\rightarrow}}v= \begin{cases}u\stackrel{{ 7k}}{{\rightarrow}}v,&u,v\in S\\ \bigcup u\stackrel{{ 7(k-1)}}{{\longrightarrow}}v^{\prime},&u\in S,v \
otin S,v^{\prime}\in in_{G}(v)\\ \bigcup u^{\prime}\stackrel{{ 7(k-1)}}{{\longrightarrow}}v,&u\
otin S,v\in S,u^{\prime}\in out_{G}(u)\\ \bigcup u^{\prime}\stackrel{{ 7(k-2)}}{{\longrightarrow}}v^{\prime},&u,v \
otin S,u^{\prime}\in out_{G}(u),v^{\prime}\in in_{G}(v)\end{cases}  \tag{3}\]  
At last, we can make a trade off in the query performance and index size for the two above approaches. Specifically, besides constructing an index for the vertices in \(S\), we also generate two-hop distance labels for the other vertices if they satisfy the predefined degree constraint. That is, when performing \(BFS\) from a vertex, \(u\), to construct a two-hop label, if the visited vertex, \(v\), satisfies \(|in_{G}(v)|>d\), then we generate \(v\)'s in-label \(L_{in}\) (\(v\)). Similarly, when performing reversed \(BFS\) from \(u\), if the visited vertex, \(v\), satisfies \(|out_{G}(v)|>d\), then we generate \(v\)'s out-label \(L_{out}(v)\). In this way, we can answer the given query using Equation (4), where \(S_{1}\) is the set of vertices satisfying \(|out_{G}(v)|>d\) and where \(S_{2}\) is the set of vertices satisfying \(|in_{G}(v)|>d\). Obviously, the given query \(u\stackrel{{ 2k}}{{\rightarrow}}v\) can be answered by calling Equation (2) at most \(d^{2}\) times (\(d>0\)). When \(d=0\), Equation (4) equals Equation (2). \[u\stackrel{{ 2k}}{{\rightarrow}}v= \begin{cases}u\stackrel{{ 2k}}{{\rightarrow}}v,&u\in S\cup S_{1}\ and\ v\in S\cup S_{2}\\ \bigcup u\stackrel{{ 7(k-1)}}{{\rightarrow}}v^{\prime},&u\in S\cup S_{1} \,,v\
otin S\cup S_{2}\,v^{\prime}\in in_{G}(v)\\ \bigcup u^{\prime}\stackrel{{ 7(k-1)}}{{\rightarrow}}v,&u\
otin S\cup S _{1}\,,v\in S\cup S_{2}\,,u^{\prime}\in out_{G}(u)\\ \bigcup u^{\prime}\stackrel{{ 7(k-2)}}{{\rightarrow}}v^{\prime},&u\
otin S\cup S _{1}\,,v\
otin S\cup S_{2}\,,u^{\prime}\in out_{G}(u),v^{\prime}\in in_{G}(v) \end{cases}  \tag{4}\]  
**Example 1:**_Figure 2 shows the comparison between different labels for \(G\) in Figure 1. From Figure 2(a), we know that constructing labels for all the vertices will result in a larger index size. As a comparison, our approach has a smaller vertex cover, \(S=\{b,\ d,\ g,\ i\}\), based on which we generate the two-hop label shown in Figure 2(b). Compared with constructing an index based on all the vertices, the index size is greatly reduced. Figure 2(c) shows the index of our degree-constraint two-hop label, which is slightly bigger than our baseline approach but is still much smaller than that of traditional two-hop distance labels._ \begin{tabular}{|c|c|c|} \hline  & \(L_{out}\) & \(L_{in}\) \\ \hline \(a\) & \((g,\ 3)\)\((d,\ 1)\)\((b,\ 0)\) & \((d,\ 2)\)\((b,\ 0)\) \\ \hline \(c\) & \((g,\ 4)\)\((d,\ 2)\)\((b,\ 1)\)\((c,\ 0)\) & \((d,\ 1)\)\((c,\ 0)\) \\ \hline \(d\) & \((g,\ 2)\)\((d,\ 0)\) & \((d,\ 0)\) \\ \hline \(e\) & \((g,\ 1)\)\((e,\ 0)\) & \((d,\ 1)\)\((e,\ 0)\) \\ \hline \(f\) & \((f,\ 0)\) & \((g,\ 1)\)\((d,\ 1)\)\((f,\ 0)\) \\ \hline \(g\) & \((g,\ 0)\) & \((g,\ 0)\) \\ \hline \(h\) & \((h,\ 0)\) & \((g,\ 1)\)\((h,\ 0)\) \\ \hline \(i\) & \((i,\ 0)\) & \((g,\ 1)\)\((i,\ 0)\) \\ \hline \(j\) & \((j,\ 0)\) & \((g,\ 2)\)\((i,\ 1)\)\((j,\ 0)\) \\ \hline \end{tabular}  \ \begin{tabular}{|c|c|c|} \hline  & \(L_{out}\) & \(L_{in}\) \\ \hline \(b\) & \((g,\ 3)\)\((d,\ 1)\)\((d,\ 2)\) \\ \hline \(d\) & \((g,\ 2)\)\((d,\ 0)\) & \((d,\ 0)\) \\ \hline \(g\) & \((g,\ 0)\) & \((g,\ 0)\) \\ \hline \(i\) & & \((g,\ 1)\) \\ \hline \(f\) & & \((g,\ 1)\)\((d,\ 1)\) \\ \hline \end{tabular}