# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 3 A Vertex-Cover-Based Approach
### Index Construction
#### 3.2.1 Vertex Cover Computation
It equals performing Case 1 twice; therefore, it can be performed in \(O(1)\) time. As a result, the overall cost of processing \(u\) is \(O(|in_{G}(u)|+|out_{G}(u)|)\). \(\square\)  
**The Algorithm:** Based on Theorem 2, we have a greedy approach shown by Algorithm 1 which sorts all the vertices by degree in line 1, initializes the hash table and the vertex cover in lines 2-3, and then computes the vertex cover in lines 4-15 by sequentially scanning array \(A\) until all the edges are removed from the graph. In each iteration (lines 4-15), Algorithm 1 sequentially fetches a vertex, \(u\), from \(A\) and adds it to the vertex cover, \(S\), in lines 5-6. In lines 7-14, we process each of \(u^{\prime}s\) neighbor, \(v\), according to Theorem 2. First, we swap \(v\) and the last vertex that has the same degree as \(v\) in line 8. In line 9, we update the hash table by reducing the end value of \(H|deg(v)|\) by one, denoting that the number of vertices with a degree \(=deg(v)\) is reduced by one. In line 10, we reduce the degree of \(v\), where \(pos(v)\) denotes the subscript of \(v\) in A. At last, we remove the edge between \(u\) and \(v\) in lines 12-13. ```
1 sort all vertices in array \(A\) by degree in decreasing order
2 initialize the end value of each degree in hash table \(H\)
3\(S\leftarrow\varnothing\) /*S is the vertex cover+/
4 while(\(E\ \
eq\varnothing\))do
5\(u\gets getNext(A)\)
6\(S\leftarrow\ S\cup\{u\}\)foreach\((v\ \in\ out_{G}(u)\) and \(v\ \inin_{G}(u))\)do
7\(v\ \leftarrow\ \text{last}\ (I(v))\) /*last \((I(v))=A[H|deg(v)]^{*}\)/
9\(H[deg(v)]\ \leftarrow\ H[deg(v)]-1\) \(deg(v)\ \leftarrow\ deg(v)-1\)
11 if\((deg(v)>A[pos(v)+1].degree)\)then\(H[deg(v)]=pos(v)\)
12 if\((v\ \in\ out_{G}(u))\)then\(E\gets E\setminus\{(u,\ v)\}\)
13 else\(E\gets E\setminus\{(v,u)\}\)
14 endfor
15 endwhile
16 returnS
```  
**Algorithm 1** CompVC \((G=(V,E))\)  
**Example 2**: _Consider \(G\) in Figure 2(a). The initial status of the corresponding array, \(A\), and the hash table, \(H\), is shown in Figure 2(a). Since all the vertices in \(A\) are sorted by degree, the first vertex to be processed is \(d\). When processing \(d\), we first add it to the vertex cover, \(S\), then process its neighbors in order \((f,\ e,\ c,\) and \(b)\). For \(f\), \(deg(f)=2\), and we first compute last \((I(f))=A[H[2]]=\ A[6]=i\) then swap vertex \(i\) and \(f\) in line 8 of Algorithm 1. After that, we update the hash value of \(H[2]\) to five due to the fact that the number of vertices with a degree = 2 is reduced by one. At last, we update\(f\)'s degree to one and remove the edge \((d,f)\) from \(E\). The other three neighbors of \(d\), i.e., \(e,\ c,\text{ and }b\), are processed similarly to \(f\). After processing all of \(d\)'s neighbors, the status of \(G\), \(A\), and \(H\) is shown in Figure 2(b). The next vertex to be processed is \(g\). The processing is similar to that of \(d\). After processing \(g\), the status of \(G\), \(A\), and \(H\) is show in Figure 2(c). The following processing is similar. After processing \(d,\ g,\ b,\text{ and }i,\text{ E becomes empty, and we know that vertex cover }S=\{d,\ g,\ b,\ i\}\)._  
As a comparison, _kReach_[10] can also compute a vertex cover in linear time. It randomly selects an edge, rather than a vertex, in each iteration and adds both vertices into \(S\), and then it deletes all the edges incident to \(u\) and \(v\). This operation repeats until all the edges are removed from \(G\). For \(G\) in Figure 1, if the edges are chosen in the order \"\((a,\ b),\ (c,d),\ (e,g),\ (i,\ j)\)\", then the vertex cover is \(S=\{a,b,c,d,e,g,i,j\}\), which is larger than the result of our approach, i.e., \(\{b,d,g,i\}\). **Analysis:** For Algorithm 1, we use an array, \(A\), to maintain all the vertices, and the size is \(O(|V|)\). Since the maximum degree is much less than \(|V|\), we know that, for Algorithm 1, the space complexity is \(O(|V|)\). Consider the time complexity. The cost of sorting operation by degree in line 1 is \(O(|V|)\) using counting sort with a space cost of \(O(|V|)\).