Reachability querying: an independent permutation labeling approach

Reachability query is a fundamental graph operation which answers whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges and has been extensively studied. In the literature, all the approaches compute a label for every vertex in a graph G by index construction offline. The query time for answering reachability queries online is affected by the quality of the labels computed in index construction. The three main costs are the index construction time, the index size, and the query time. Some of the up-to-date approaches can answer reachability queries efficiently, but spend nonlinear time to construct an index. Some of the up-to-date approaches construct an index in linear time and space, but may need to depth-first search G at run-time in \(O(n + m)\). In this paper, we discuss a new randomized labeling approach, named IP label, to answer reachability queries with probability guarantee, and the randomness is by independent permutation. Two additional labels are also proposed to further enhance the query processing. In addition, to deal with dynamic graphs, we discuss the label maintenance over dynamic graphs and give efficient algorithms for the labels proposed. We conduct extensive experimental studies to compare with the up-to-date approaches using 19 large real datasets used in the existing work and synthetic datasets. We confirm the efficiency and scalability of our approach in static graphs testing, and our maintenance algorithms are about one order of magnitude faster than the existing ones in dynamic graphs testing.