# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 3 A Vertex-Cover-Based Approach
### Index Construction
#### 3.2.1 Vertex Cover Computation  
The vertex cover, \(S\), in our approach should satisfy two conditions: (1) When selecting a vertex and adding it into \(S\) in each iteration, the selected vertex should be the one covering the largest number of uncovered edges. In this way, we can obtain a smaller vertex cover to reduce the two-hop index size. Assuming that, after a vertex is processed, all the edges incident to it will be deleted, we know that the number of uncovered edges with respect to a vertex is its current degree. Therefore, the selected vertex in each iteration is the one with the largest degree among all the remaining vertices in \(V\backslash S\), i.e., \(u\)'s degree is the number of out- and in-neighbors that do not belong to \(S\). (2) It should be computed efficiently. If we want to satisfy the first condition, it means that, after choosing a vertex, \(u\), and adding it to \(S\), we need to change the degree of \(u\)'s out- and in-neighbors and then perform a sorting operation so that, in the next iteration, we can find the vertex that has the largest degree on the fly. If we calculate it using a priority queue, the cost of computing the vertex cover is \(O(|E|\ log|V|)\). Here, we propose a novel approach which guarantees that if a vertex cover satisfies the first condition, it can be computed in linear time \(O(|V|+|E|)\). We first sort all the vertices in descending order with respect to their degrees. We use an array, \(A\), to maintain the sorting result. For each degree, there may exist many vertices that have the same degree in \(A\). We use a hash table, \(H\), to record for these vertices with the same degree, \(d\), the position of the last vertex in \(A\) (the subscript of the last vertex). For example, for \(G\) in Figure 3a, the array, \(A\), and the hash table, \(H\), are shown in Figure 3a. For \(G\), there are two vertices with a degree = 4, i.e., \(d\) and \(g\). \(H[4]\) = 1 means that, in \(A\), for the vertices with a degree = 4, the position of the last one is one, denoting vertex \(g\). When we take a vertex, \(u\), and add it to \(S\), we need to update the degree of \(u\)'s neighbors then adjust their positions in \(A\) and update \(H\). Figure 3: Running status of Algorithm 1, where (**a**) shows the initial status before processing any vertex and where (**b**–**e**) are the status after processing \(d\), \(g\), \(b\), and \(i\), respectively. In each subfigure, \(A\) is the array maintaining the vertices after sorting operation by degree, and \(H\) is the hash table. **Theorem 2**. : _Let \(u\) be the vertex with the largest degree. The operation of removing \(u\) from the given graph, \(G\), and sorting all the remaining vertices according to their new degrees can be performed with a cost of \(O(|in_{G}(u)|+|out_{G}(u)|)\)._  
Proof of Theorem 2.: Let \(v\) be one of \(u\)'s in- or out-neighbors, and let \(I(v)\) be the set of vertices in \(A\) that have the same degree as \(v\). When we remove \(u\) from \(G\), \(v\)'s degree will decrease by one (Case 1) or by two (Case 2). Case 1 means that there exists an edge, \((u,v)\) or \((v,u)\), and Case 2 means that both \((u,v)\) and \((v,u)\) exist. Consider Case 1. Before deleting \(u\), all the vertices in \(A\) are sorted by degree. Because the vertex, \(w\), after the last vertex of \(I(v)\) has a degree satisfying \(deg(v)>deg(w)\), we only need to swap \(v\) and the last vertex of \(I(v)\), which guarantees that, after \(u\) is deleted, all the vertices of \(I(v)\) have the same degree and that their positions in \(A\) are still continuous. After the adjustment, we update the hash table by reducing the end value of \(H|deg(v)|\) by one, i.e., \(H|deg(v)|=H|deg(v)|-1\), denoting that the size of \(I(v)\) is reduced by one. Then, if \(deg(v)>deg(w)\), it means that \(I(v)=\{\,v\,\}\) and that we need to add a new entry into \(H\), i.e., \(H|deg(v)|=pos(v)\). Therefore, the cost of processing \(u^{\prime}s\) neighbor, \(v\), is \(O(1)\). Consider Case 2.