Problema de alcançabilidade em grafos muito grandes: Aplicação, complexidade e algoritmos

Abstract

Given a directed acyclic graph G=(V,E) and two vertices u, v in V, the reachability problem is to answer if is it possible to reach v from u by transversing the edges of the graph. For very large graphs, with millions of vertices, it is infeasible to search the graph for each query and it is also infeasible to store the transitive closure of the graph since it is squared in terms of space. Then, scalable approaches aim to generate good indexes used to prune the search during its execution in the graph. In this work, we formalize the One-Sided Weak Dominance Drawing Problem which is already used informally in the literature to construct this kind of indexes and we also prove that this problem is NP-Complete. Next, we identify oportunities for improvement on main approaches for the problem. We propose a novel scalable approach called LYNX that uses a large number of topological sorts of the graph as a negative cut index without degrading the query time. A similar strategy is applied regarding the positive cut index. In addition, LYNX proposes a user-defined index size that enables the user to control the ratio between negative and positive cut depending on the expected query pattern. We show by computational experiments that LYNX outperforms the state-of-the-art approach in terms of query-time using the same index-size for graphs with high reachability ratio.