One Edge at a Time: A Novel Approach Towards Efficient Transitive Reduction Computation on DAGs

摘要

Given a directed acyclic graph (DAG) G, G's transitive reduction (TR) Gtr is the unique DAG satisfying that Gtr has the minimum number of edges and has the same transitive closure (TC) as G. TR computation has been extensively studied during the past decades and was used in many applications, where the main problem is how to compute TR efficiently for large graphs. However, existing approaches have either large space complexity or higher time complexity, which makes them cannot compute TR efficiently on large dense graphs. We propose a novel approach for TR computation, which takes every single edge as the basic processing unit, and utilizes existing reachability algorithms to test whether it is redundant or not. In this way, we avoid the costly graph traversal operation of existing approaches. We identify the performance bottleneck and propose a set of heuristics to sort edges, such that to reduce the average processing cost of each edge. We show by experimental results that our approach works much better than all the existing approaches, and can be faster than the state-of-the-art approach by more than two orders of magnitude on large dense graphs.