# Efficient Processing of \(k\)-Hop Reachability Queries on Directed Graphs
## 2 Related Work  
Given a directed graph, \(G=(V,E)\), where \(V\) denotes the set of vertices and where \(E\) denotes the set of edges, an edge \((u,v)\in E\) denotes a directed edge from vertex \(u\) to \(v\). In this context, \(u(v)\) is referred to as the in-neighbor (out-neighbor) of \(v(u)\). We use \(d(u,v)\) to represent the length of the shortest simple path \(p_{u,v}\) from \(u\) to \(v\), i.e., the number of edges in \(p_{u,v}\). In the following, we discuss the related work on kHRQs. **Query Processing on General Directed Graphs:** The two recent approaches for addressing kHRQs on general directed graphs with _SCCs_ are _kReach_[10; 11] and _ESTI_[12]. _kReach_[10; 11] is the first approach tailored to answering kHRQs in such graphs, and it precomputes \(k\)-hop reachability information among a set of vertices to facilitate answering these queries. When letting \(d_{max}=max\{d(u,v)|u,v\in V\}\), the basic _kReach_ needs to construct \(d_{max}\) distinct indexes. Here, each index is a graph of \(G_{K}=(V_{k},E_{k})(k\in[1,\ d_{max}])\), where \(V_{k}\) is the vertex cover and where \(E_{k}=\{(u,v)|u,v\in V_{k},d(u,v)\leq k\}\). Each edge, \((u,v)\in E_{k}\), is associated with a weight denoting the length from \(u\) to \(v\). Given a query, \(u\stackrel{{\gamma_{k}}}{{\rightarrow}}v\), \(G_{k}\) can only be used to answer whether there exists a path from \(u\) to \(v\) with a length \(\leq k\) without graph traversal. In practice, the basic _kReach_ cannot scale to large graphs to process queries with a general \(k\) due to a large storage space. An improvement for this is building the index on a single vertex cover, \(S\). However, to answer general kHRQs, it needs to compute the lengths of the shortest paths for each pair of vertices in \(S\). Still, such an improvement suffers from a \(O(|S|^{2})\) index size and cannot scale to graphs where \(S\) becomes large. Considering this, the optimized _kReach_[10; 11] uses the \(k\)-relaxed partial vertex cover to reduce the index size; such a strategy also means that many queries are answered with the costly operation of graph traversal, and the query performance degenerates accordingly. Hereafter, when we say _kReach_, it denotes the optimized approach that can process large graphs. ESTI_[12] is an extended spanning tree index combined with two topological orders [4]. The spanning tree index is used to compute the distance, and the two topological orders are used to prune unreachable queries. For _ESTI_, as the spanning tree index is constructed by _BFS_ and as the size of the _ESTI_ index is equal to the number of edges in the input graph, queries are usually answered depending on the costly graph traversal operation, and the query performance degenerates sharply, especially when the graph becomes dense. **Query Processing on DAGs:** On top of _ESTI_ and _kReach_, there are also other approaches, such as _BFSI-B_[13] and _HT_[14], that can be used to answer kHRQs. However, both _BFSI-B_ and _HT_ can only work on _DAGs_; they cannot be applied to graphs with SCCs. The reason lies in that they both use topological orders to check the unreachability from the source vertex to the target vertex. Further, _HT_ uses a topological level to check the unreachability relationship between the source vertex and the target vertex, which also cannot be applied to a directed graph. Note that a traditional reachability query is a special case of kHRQs where \(k=\infty\), therefore the approaches for traditional reachability queries [2; 4; 5; 17; 18; 19; 20] cannot be used to answer kHRQs. Other than the above approaches that focus on processing kHRQs, [21] studied the problem of answering reachability queries with label constraints, and [22] tried to enumerate for two vertices all the paths between them with lengths smaller than a predefined threshold.