Answering reachability queries is a fundamental graph operation. Considering that the size of the input graph has a great impact on query performance, there are studies focusing on reducing the graph size, such that queries can be answered over a smaller graph. Although the input graph can be compressed significantly by existing approaches, a good compression ratio does not always mean a positive effect on query performance. In this paper, we study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely RCN reduction, to compress the input graph into a smaller one. Let a be the compression ratio of the number of nodes in the reduced graph over that of the input graph, we show that based on our approach, the lower bound probability that a query q can be answered in constant time is 1-a^2. We show the difficulties of RCN reduction and propose efficient algorithms to improve the compression ratio. Based on the result of RCN reduction, we further propose a novel labeling scheme to accelerate queries answering. We confirm the efficiency of our approach by extensive experimental results for graph reduction and reachability queries processing using 20 real datasets.

We study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely RCN reduction, to reduce the input graph$G$of$\vert V\vert$nodes into a smaller one with$\vert V^{r}\vert$nodes. Assume that the probability of a node of$G$to be a query node is$1/\vert V\vert$, we show that based on our approach, the lower bound probability that a query$q$can be answered in constant time is$1-(\frac{\vert V^{r}\vert}{\vert V\vert})^{2}$, denoting that the smaller the reduced graph, the larger the probability that$q$can be answered in constant time. We show the difficulties of RCN reduction and propose efficient algorithms to improve the reduction ratio. We confirm the benefits of our approach by rich experimental results using real datasets.