# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 3 A Vertex-Cover-Based Approach  
### Overview  
To improve the query performance, our approach is to construct a novel two-hop distance label. The novelty of our labeling lies in that, before index construction, we firstly obtained a small set, \(S\), of vertices based on which we generated two-hop distance labels with a smaller index size that covered all reachability information. We show below that, even if \(|S|\ll|V|\), our approach can still guarantee the avoidance of the costly graph traversal. **Definition 1**. : _Given a directed edge, \(e=(u,v)\), \(e\) is covered by a vertex if it is either \(u\) or \(v\)._  
**Definition 2**. : _Given a directed graph, \(G=(V,E)\), a vertex cover, \(S\), of \(G\) is a subset of \(V\), satisfying that every edge of \(E\) is covered by at least one vertex of \(S\)._  
According to Definition 1, the number of covered edges for a vertex, \(v\), is \(|in_{G}(v)\cup out_{G}(v)|\). For \(G\) in Figure 1, \(S=\{a,b,c,d,e,g,i,j\}\) is a cover set according to Definition 2. Note that for a directed graph, \(G\), the vertex cover is not unique. It is easy to verify that, for \(G\), \(V\) is a vertex cover. **Theorem 1**. : _Given a directed graph, \(G\), and one of its vertex covers, \(S\), any kHRQ can be answered with the two-hop distance labels generated from \(S\)._  
Proof of Theorem 1.: Given a query, \(u\stackrel{{\gamma_{k}}}{{\rightarrow}}v\), we prove this result with two aspects. Case 1: if \(u\) belongs to \(S\), then we need to construct a two-hop label from \(u\) by performing bidirectional \(BFS\); that is, we know the distance from \(u\) to any vertex that \(u\) can reach or be reached by, which is maintained in the two-hop distance labels. Thus, we know the distance, \(d(u,v)\), due to Equation (1). If \(d(u,v)\leq k\), then the answer is TRUE; otherwise, the answer is FALSE. Symmetrically, if \(v\) belongs to \(S\), we obtain the same result. Case 2: if none of \(u\) or \(v\) belongs to \(S\), then all the vertices in \(out_{G}(u)\) and \(in_{G}(u)\) belong to \(S\); otherwise, there exists at least one edge that cannot be covered by \(S\) according to Definition 2. Therefore, the distance from any vertex of \(out_{G}(u)\cup in_{G}(u)\) to all the other vertices can be computed by Case 1. Then, through Equation (1), we can obtain \(d(u,v)\). According to Theorem 1, the two-hop label constructed from the vertices in \(S\) can be used to obtain the answers for all kHRQs. Since \(S\subseteq V\) and since [16] constructs two-hop labels from all vertices, the index size can be reduced if we construct the two-hop index from \(S\). The smaller \(S\) is, the smaller the index size is. As finding the minimum vertex cover is NP-hard [23], we propose a linear-time approach to find a smaller vertex cover by choosing in each iteration the vertex that covers more uncovered edges. Here, the key problem is how to determine which vertex can cover more uncovered edges in \(O(1)\) time to achieve linear-time complexity. The details are discussed in Section 3.2.1. After finding the vertex cover, \(S\), we can build two-hop distance labels. Here, we have three choices. One is to use the vertices of \(S\) to generate labels for the vertices in \(V\) so that a given query, \(u\stackrel{{\gamma_{k}}}{{\rightarrow}}v\), can be answered with Equation (2). To do so, we need to construct two-hop distance labels for all the vertices, which may still result in a large index size. \[u\stackrel{{\gamma_{k}}}{{\rightarrow}}v=\left\{ \begin{array}{ ll}TRUE,d(u,v)\leq k\\ FALSE,otherwise\end{array} \right. \tag{2}\]  
The other is to use \(S\) to construct labels for the vertices in \(S\). For the vertices that belong to \(V\setminus S\), no labels are generated. Intuitively, the index size can be reduced greatly. As the vertices belonging to \(V\setminus S\) do not have a two-hop distance label, we need to answer the  
Figure 1: A sample directed graph, G.  
given query with Equation (3).